論文の概要: A Simulated Annealing-Based Multiobjective Optimization Algorithm for
Minimum Weight Minimum Connected Dominating Set Problem
- arxiv url: http://arxiv.org/abs/2312.11527v1
- Date: Wed, 13 Dec 2023 13:36:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-31 03:43:46.681429
- Title: A Simulated Annealing-Based Multiobjective Optimization Algorithm for
Minimum Weight Minimum Connected Dominating Set Problem
- Title（参考訳）: 最小重量最小連結ドーティング集合問題に対するシミュレーションアニーリングに基づく多目的最適化アルゴリズム
- Authors: Hayet Dahmri and Salim Bouamama
- Abstract要約: 本稿では,最小連結支配問題の変種に対処するための欲求に基づくシミュレーションアルゴリズムを提案する。
近年の研究では,本手法の優位性について検討した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Minimum connected dominating set problem is an NP-hard combinatorial
optimization problem in graph theory. Finding connected dominating set is of
high interest in various domains such as wireless sensor networks, optical
networks, and systems biology. Its weighted variant named minimum weight
connected dominating set is also useful in such applications. In this paper, we
propose a simulated annealing algorithm based on a greedy heuristic for
tackling a variant of the minimum connected dominating set problem and that by
exploiting two objectives together namely the cardinality and the total weight
of the connected dominating set. Experimental results compared to those
obtained by a recent proposed research show the superiority of our approach.
- Abstract（参考訳）: 最小連結支配集合問題は、グラフ理論におけるNPハード組合せ最適化問題である。
接続された支配集合を見つけることは、無線センサネットワーク、光ネットワーク、システム生物学など様々な分野に高い関心を持っている。
その重み付き変種である最小重み付き支配集合はそのような応用にも有用である。
本稿では,最小連結ドミネート集合の変種に取り組むためのグリーディヒューリスティックに基づくシミュレーションアニーリングアルゴリズムを提案し,連結ドミネート集合の濃度と総重量の2つの目的を同時に利用する。
最近の研究で得られたものと比較した実験結果から,本手法の優越性が示された。
関連論文リスト
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - Equivariant Deep Weight Space Alignment [54.65847470115314]
本稿では,ウェイトアライメント問題を解決するための学習を目的とした新しいフレームワークを提案する。
まず、重み調整が2つの基本対称性に一致することを証明し、それからこれらの対称性を尊重する深いアーキテクチャを提案する。
論文 参考訳（メタデータ） (2023-10-20T10:12:06Z) - Learning-Based Heuristic for Combinatorial Optimization of the Minimum
Dominating Set Problem using Graph Convolutional Networks [1.5469452301122175]
グラフ $mathcalG=(V, E) の支配集合は、支配集合の外側の頂点集合 $SsubseteqmathcalV setminus S$ の部分集合である。
本稿では,グラフ$畳み込みネットワークを用いた最小支配集合問題に対する学習に基づく新しい解法を提案する。
論文 参考訳（メタデータ） (2023-06-06T06:22:42Z) - Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum
Weight Base Problems [16.803653908913514]
本稿では,多目的最小重み付け木問題などの古典的NPハード問題を抽象化した多目的最小重み付け木問題について検討する。
極点数に対する近似品質や上限値など,非支配面の凸殻のいくつかの重要な性質を証明した。
適切な設定でMOEA/Dアルゴリズムは、オラクルモデルにおいて期待される固定対象時間内の全ての極端点を求める。
論文 参考訳（メタデータ） (2023-06-06T05:13:29Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。
我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。
アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
論文 参考訳（メタデータ） (2022-10-31T17:59:29Z) - End-to-End Pareto Set Prediction with Graph Neural Networks for
Multi-objective Facility Location [10.130342722193204]
施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。
本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。
ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
論文 参考訳（メタデータ） (2022-10-27T07:15:55Z) - 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) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。