論文の概要: Computing Diverse Shortest Paths Efficiently: A Theoretical and
Experimental Study
- arxiv url: http://arxiv.org/abs/2112.05403v1
- Date: Fri, 10 Dec 2021 09:21:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-13 15:30:34.544057
- Title: Computing Diverse Shortest Paths Efficiently: A Theoretical and
Experimental Study
- Title（参考訳）: 計算最短経路の有効性:理論的および実験的研究
- Authors: Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota
Otachi
- Abstract要約: 有向グラフにおいて最短の$st$-pathを求めるアルゴリズムを提案する。
また, 多様な重み付きマトロイド基底, 多様な重み付きアーボラッセンス, 多様な二部体マッチングなどの古典的問題の多様性について検討した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding diverse solutions in combinatorial problems recently has received
considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al.
2021). In this paper we study the following type of problems: given an integer
$k$, the problem asks for $k$ solutions such that the sum of pairwise
(weighted) Hamming distances between these solutions is maximized. Such
solutions are called diverse solutions. We present a polynomial-time algorithm
for finding diverse shortest $st$-paths in weighted directed graphs. Moreover,
we study the diverse version of other classical combinatorial problems such as
diverse weighted matroid bases, diverse weighted arborescences, and diverse
bipartite matchings. We show that these problems can be solved in polynomial
time as well. To evaluate the practical performance of our algorithm for
finding diverse shortest $st$-paths, we conduct a computational experiment with
synthetic and real-world instances.The experiment shows that our algorithm
successfully computes diverse solutions within reasonable computational time.
- Abstract（参考訳）: 近年,組合せ問題における多様な解の発見が注目されている(Baste et al. 2020, Fomin et al. 2020, Hanaka et al. 2021)。
整数 $k$ が与えられたとき、これらの解間のペアワイズ(重み付けされた)ハミング距離の和が最大化されるような$k$の解を求める。
このような解は多様な解と呼ばれる。
重み付き有向グラフにおいて最短の$st$パスを求める多項式時間アルゴリズムを提案する。
さらに,多彩な重み付きマトロイド基底,多彩な重み付きアルブレッセンス,多様な二成分マッチングなど,他の古典的組合せ問題についても検討した。
これらの問題を多項式時間で解くことができることを示す。
提案手法の実用的性能を評価するために,我々は合成および実世界のインスタンスを用いた計算実験を行い,提案手法が妥当な計算時間内に多様な解をうまく計算できることを示した。
関連論文リスト
- A $Δ$-evaluation function for column permutation problems [0.0]
新しい$Delta$-evaluation法は、連続する性質を持つスパース二元行列上で定義された列置換問題を解くために導入された。
この問題はグラフ理論と工業生産の文脈における様々な$mathcalNP$-hard問題をモデル化する。
提案手法は一般に競争力があり,特に大規模かつ高密度なインスタンスに有用である。
論文 参考訳（メタデータ） (2024-09-07T22:50:25Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。
EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。
我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
論文 参考訳（メタデータ） (2024-05-16T15:11:37Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Multilevel Memetic Hypergraph Partitioning with Greedy Recombination [0.0]
KaHyPar-Eはハイパーグラフ分割問題のために設計された最初のマルチレベルメメティック計算アルゴリズムである。
問題固有のリコンビネーションと突然変異演算子を導入し,KaHyPar-Eとそれらの演算子を組み合わせることで,新しいマルチレベルメメティックアルゴリズムを開発した。
我々のアルゴリズムは他のすべてより優れていて、最高のソリューションは12ドル、15ドル、25ドル、それぞれ2ドル、4ドル、そして8ドルだ。
論文 参考訳（メタデータ） (2022-04-07T20:45:17Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Power of human-algorithm collaboration in solving combinatorial
optimization problems [0.0]
最適化問題のクラスは、$epsilon$ が任意の定数であるような乗法係数 $epsilon$ を期待して、効率的に解けることを示す。
提案手法は単に理論的なものであるに過ぎないが、通常は難解であると考えられるこれらの問題を解決する方法に新たな光を当てた。
論文 参考訳（メタデータ） (2021-07-25T11:21:59Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Curriculum learning for multilevel budgeted combinatorial problems [7.804994311050265]
マルチレベル最適化問題はそれらの一般化であり、複数のプレイヤーが逐次決定を下す状況を含んでいる。
グラフ上のゼロサムゲームにおいて、2人のプレイヤーが関与する多段階の予算問題を解決するための価値ベース手法を考案する。
我々のフレームワークは単純なカリキュラムに基づいており、もしエージェントが$B$までの予算を持つインスタンスの価値を見積もる方法を知っているなら、可能なすべての余剰状態の方向に関係なく、予算が$B+1$のインスタンスを時間内に解決することができる。
論文 参考訳（メタデータ） (2020-07-07T01:09:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。