論文の概要: A Dual-mode Local Search Algorithm for Solving the Minimum Dominating Set Problem

• arxiv url: http://arxiv.org/abs/2307.16815v1
• Date: Tue, 25 Jul 2023 15:19:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-06 11:22:01.121669
• Title: A Dual-mode Local Search Algorithm for Solving the Minimum Dominating Set Problem
• Title（参考訳）: 最小支配集合問題の解法のための2モード局所探索アルゴリズム
• Authors: Enqiang Zhu, Yu Zhang, Shengzhi Wang, Darren Strash, and Chanjuan Liu
• Abstract要約: MinDS問題は従来の$mathcalNP$-hard問題であり、ネットワーク解析における多くの異なる応用のために広く研究されている。 既存のMinDSアルゴリズムは常に、頂点を選択する際、様々なタイブリングケースによって制限される。 本稿では,DmDSと呼ばれるMinDS問題に対する効率的な局所探索アルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 4.145008274947301
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a graph, the minimum dominating set (MinDS) problem is to identify a smallest set $D$ of vertices such that every vertex not in $D$ is adjacent to at least one vertex in $D$. The MinDS problem is a classic $\mathcal{NP}$-hard problem and has been extensively studied because of its many disparate applications in network analysis. To solve this problem efficiently, many heuristic approaches have been proposed to obtain a good solution within an acceptable time limit. However, existing MinDS heuristic algorithms are always limited by various tie-breaking cases when selecting vertices, which slows down the effectiveness of the algorithms. In this paper, we design an efficient local search algorithm for the MinDS problem, named DmDS -- a dual-mode local search framework that probabilistically chooses between two distinct vertex-swapping schemes. We further address limitations of other algorithms by introducing vertex selection criterion based on the frequency of vertices added to solutions to address tie-breaking cases, and a new strategy to improve the quality of the initial solution via a greedy-based strategy integrated with perturbation. We evaluate DmDS against the state-of-the-art algorithms on seven datasets, consisting of 346 instances (or families) with up to tens of millions of vertices. Experimental results show that DmDS obtains the best performance in accuracy for almost all instances and finds much better solutions than state-of-the-art MinDS algorithms on a broad range of large real-world graphs.
• Abstract（参考訳）: グラフが与えられたとき、最小支配集合(MinDS)問題は、$D$にないすべての頂点が$D$の少なくとも1つの頂点に隣接しているような最小セットの頂点を識別することである。 MinDS問題は古典的な$\mathcal{NP}$-hard問題であり、ネットワーク解析における多くの異なる応用のために広く研究されている。 この問題を効率的に解くために、許容時間内に良い解を得るための多くのヒューリスティックなアプローチが提案されている。 しかし、既存のMinDSヒューリスティックアルゴリズムは、アルゴリズムの有効性を遅くする頂点を選択する際に、常に様々なタイブリングケースによって制限される。 本稿では,2つの異なる頂点スワッピング方式を確率的に選択するデュアルモード局所探索フレームワークであるDmDSという,MinDS問題の効率的な局所探索アルゴリズムを設計する。 さらに, 解に付加される頂点の頻度に基づく頂点選択基準を導入することで, 他のアルゴリズムの限界にも対処し, 摂動と統合した欲望に基づく戦略を通じて初期解の品質を向上させる新たな戦略を提案する。 最大数千万の頂点を持つ346のインスタンス(または家族)からなる7つのデータセット上で、最先端のアルゴリズムに対してDmDSを評価する。 実験結果から,DmDSの精度は,ほぼすべての事例において最良であり,大規模な実世界のグラフ上での最先端のMinDSアルゴリズムよりもはるかに優れた解が得られた。

関連論文リスト

• Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [9.01394829787271]
  クラスタリングに基づく最大内部積探索(MIPS)におけるルーティングの問題について検討する。 最大内積を楽観的に推定するために,各シャード内の内積分布のモーメントを組み込んだ新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2024-05-20T17:47:18Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  本稿では,候補アルゴリズムの集合に有効な手法を提案する。 内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。 提案手法は,他のアルゴリズムのスコアを大幅に改善する。
  論文  参考訳（メタデータ） (2023-05-26T21:49:37Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems [9.653157073271021]
  我々は、min-max最適化問題を解決するために、分散適応運動量 (ADAM) 型アルゴリズムを開発した。 我々は、(確率的な)一階のナッシュ平衡点を求めるための提案アルゴリズムの非漸近収束率を求める。
  論文  参考訳（メタデータ） (2021-06-10T22:32:01Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on Clustered Shortest-Path Tree problem [2.578242050187029]
  CluSPT(Clustered Shortest-Path Tree Problem)はNPハード問題である。 探索処理の性能を向上させるために,2つの手法を提案する。
  論文  参考訳（メタデータ） (2020-10-19T08:37:18Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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