論文の概要: 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アルゴリズムの改善につながることを期待しています。

関連論文リスト

• Pathfinding with Lazy Successor Generation [12.02023514105999]
  位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。 単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。 そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
  論文  参考訳（メタデータ） (2024-08-27T23:25:25Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。 ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。 これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
  論文  参考訳（メタデータ） (2024-06-07T13:42:15Z)
• Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [9.01394829787271]
  クラスタリングに基づく最大内部積探索(MIPS)におけるルーティングの問題について検討する。 最大内積を楽観的に推定するために,各シャード内の内積分布のモーメントを組み込んだ新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2024-05-20T17:47:18Z)
• 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)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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