論文の概要: A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems
- arxiv url: http://arxiv.org/abs/2203.15805v1
- Date: Mon, 28 Mar 2022 21:34:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-01 08:24:04.806998
- Title: A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems
- Title(参考訳): 最大重み独立集合問題に対するメタヒューリスティックアルゴリズム
- Authors: Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis,
Mauricio G.C. Resende, Quico Spaen
- Abstract要約: ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
- 参考スコア(独自算出の注目度): 58.348679046591265
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by a real-world vehicle routing application, we consider the
maximum-weight independent set problem: Given a node-weighted graph, find a set
of independent (mutually nonadjacent) nodes whose node-weight sum is maximum.
Some of the graphs airsing in this application are large, having hundreds of
thousands of nodes and hundreds of millions of edges. To solve instances of
this size, we develop a new local search algorithm, which is a metaheuristic in
the greedy randomized adaptive search (GRASP) framework. This algorithm, which
we call METAMIS, uses a wider range of simple local search operations than
previously described in the literature. We introduce data structures that make
these operations efficient. A new variant of path-relinking is introduced to
escape local optima and so is a new alternating augmenting-path local search
move that improves algorithm performance. We compare an implementation of our
algorithm with a state-of-the-art openly available code on public benchmark
sets, including some large instances with hundreds of millions of vertices. Our
algorithm is, in general, competitive and outperforms this openly available
code on large vehicle routing instances. We hope that our results will lead to
even better MWIS algorithms.
- Abstract(参考訳): ノード重み付きグラフが与えられた場合、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
このサイズの例を解決するために, greedy randomized adaptive search (grasp) フレームワークにおけるメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
このアルゴリズムはmetamisと呼ばれ、以前に文献に記述したよりも、より広い範囲の単純なローカル検索操作を使用する。
これらの操作を効率的にするデータ構造を導入します。
局所的最適から逃れるために新しいパスリリンクを導入し、アルゴリズム性能を改善する新しい交互拡張パスローカル検索も導入した。
我々は,アルゴリズムの実装を,数億の頂点を持つ大規模インスタンスを含む,公開ベンチマークセット上の最先端の公開コードと比較した。
我々のアルゴリズムは一般に競争力があり、大規模な車両ルーティングインスタンス上でこの公開コードより優れています。
結果がMWISアルゴリズムの改善につながることを期待しています。
関連論文リスト
- A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman
Problem [0.9790236766474201]
本稿では,Multiple Traveling Salesman Problem (mTSP) を解くためのハイブリッド遺伝的アルゴリズムを提案する。
新たなクロスオーバーオペレーターは、2人の親からの同様のツアーを組み合わせるように設計されており、人口に対して大きな多様性を提供する。
我々のアルゴリズムは、ベンチマークセットに対してテストした場合に、同様のカットオフ時間しきい値で、すべての既存のアルゴリズムを平均で上回ります。
論文 参考訳(メタデータ) (2023-07-14T01:57:10Z) - ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate
Nearest Neighbor Search Algorithms [5.478671305092084]
本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。
我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
論文 参考訳(メタデータ) (2023-05-07T19:28:23Z) - Finding and Exploring Promising Search Space for the 0-1
Multidimensional Knapsack Problem [18.19836641663039]
0-1 多次元クナップサック問題(MKP)は、多くの工学的応用において古典的なNPハード最適化問題である。
我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-08T05:11:47Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳(メタデータ) (2021-04-14T18:15:27Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳(メタデータ) (2020-12-04T15:46:30Z) - 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) - LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set
Similarity Under Skew [58.21885402826496]
全ペアセットの類似性は、大規模で高次元のデータセットであっても広く使われているデータマイニングタスクである。
我々は,全対集合の類似性を近似するために,新しい分散アルゴリズム LSF-Join を提案する。
LSF-Joinは、小さな類似度閾値やスキュー入力セットであっても、最も近いペアを効率的に見つける。
論文 参考訳(メタデータ) (2020-03-06T00:06:20Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。