論文の概要: Evolving test instances of the Hamiltonian completion problem

• arxiv url: http://arxiv.org/abs/2011.02291v2
• Date: Mon, 18 Jan 2021 19:28:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 20:02:11.324523
• Title: Evolving test instances of the Hamiltonian completion problem
• Title（参考訳）: ハミルトニアン完備問題(hamiltonian completion problem)の変遷
• Authors: Thibault Lechien, Jorik Jooken, Patrick De Causmaecker
• Abstract要約: 本稿では,進化的アルゴリズムを用いて多様なインスタンス群を生成する手法を提案する。 得られたグラフを分析し、どの属性がアルゴリズムのパフォーマンスに最も関連しているかについて重要な洞察を得る。
• 参考スコア（独自算出の注目度）: 0.7734726150561086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Predicting and comparing algorithm performance on graph instances is challenging for multiple reasons. First, there is usually no standard set of instances to benchmark performance. Second, using existing graph generators results in a restricted spectrum of difficulty and the resulting graphs are usually not diverse enough to draw sound conclusions. That is why recent work proposes a new methodology to generate a diverse set of instances by using an evolutionary algorithm. We can then analyze the resulting graphs and get key insights into which attributes are most related to algorithm performance. We can also fill observed gaps in the instance space in order to generate graphs with previously unseen combinations of features. This methodology is applied to the instance space of the Hamiltonian completion problem using two different solvers, namely the Concorde TSP Solver and a multi-start local search algorithm.
• Abstract（参考訳）: グラフインスタンス上でのアルゴリズム性能の予測と比較は、複数の理由から難しい。 まず、パフォーマンスをベンチマークするインスタンスの標準セットは、通常存在しない。 第二に、既存のグラフ生成器を使用すると、困難なスペクトルが制限され、結果として得られるグラフは通常、音の結論を引き出すのに十分な多様性がない。 そこで最近の研究は、進化的アルゴリズムを用いて多様なインスタンス群を生成する新しい手法を提案する。 そして、結果のグラフを分析し、どの属性がアルゴリズムのパフォーマンスに最も関連しているかに関する重要な洞察を得ることができます。 以前は目に見えない機能の組み合わせでグラフを生成するために、インスタンス空間の観測されたギャップを埋めることもできる。 この手法は、2つの異なる解法、すなわち Concorde TSP Solver とマルチスタート局所探索アルゴリズムを用いてハミルトン完備化問題のインスタンス空間に適用する。

関連論文リスト

• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  複素構造特性をチェックできるグラフ同型を一般化する。 この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。 本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-15T18:12:44Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• A Comparative Study of Graph Matching Algorithms in Computer Vision [42.041759337188914]
  本稿では,グラフマッチングアルゴリズムの比較研究について述べる。 我々は,既存のコンピュータビジョングラフマッチング問題の多くを収集し,分類するベンチマークを作成する。 同時に、グラフマッチングアルゴリズムの最も人気のあるオープンソース実装を収集、分類する。
  論文  参考訳（メタデータ） (2022-07-01T09:37:34Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm [20.582965700659788]
  我々は、最も単純なアルゴリズムであるGREEDYの競合比を、関連する離散過程を連続的に近似することによって推定する。 驚くべきことに、GREEDYは、オンラインマッチングのためのもう1つの有名なアルゴリズムであるRANKINGよりも優れたパフォーマンスを保証することができる。
  論文  参考訳（メタデータ） (2021-07-02T12:18:19Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。 複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。 これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
  論文  参考訳（メタデータ） (2021-03-25T14:35:07Z)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。 We show that our method with depth $w$ run in $O(pw+3) $ time。 また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-06T21:56:41Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。