論文の概要: Solving the Steiner Tree Problem with few Terminals
- arxiv url: http://arxiv.org/abs/2011.04593v1
- Date: Mon, 9 Nov 2020 17:46:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-28 01:54:25.600958
- Title: Solving the Steiner Tree Problem with few Terminals
- Title（参考訳）: 少数の端末でシュタイナー木問題を解決する
- Authors: Johannes K. Fichte, Markus Hecher, Andre Schidler
- Abstract要約: 動的プログラミングによるスタイナーツリー問題の解法として、Dijkstra-Steinerアルゴリズムがある。
我々はDijkstra-Steinerアルゴリズムを強化し、DS*と呼ばれる再検討アルゴリズムを確立する。
そこで本研究では,DS* アルゴリズムの適合性は整合性よりも弱いことを示し,許容関数を用いた場合の正当性を確立する。
- 参考スコア（独自算出の注目度）: 8.024778381207128
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Steiner tree problem is a well-known problem in network design, routing,
and VLSI design. Given a graph, edge costs, and a set of dedicated vertices
(terminals), the Steiner tree problem asks to output a sub-graph that connects
all terminals at minimum cost. A state-of-the-art algorithm to solve the
Steiner tree problem by means of dynamic programming is the Dijkstra-Steiner
algorithm. The algorithm builds a Steiner tree of the entire instance by
systematically searching for smaller instances, based on subsets of the
terminals, and combining Steiner trees for these smaller instances. The search
heavily relies on a guiding heuristic function in order to prune the search
space. However, to ensure correctness, this algorithm allows only for limited
heuristic functions, namely, those that satisfy a so-called consistency
condition. In this paper, we enhance the Dijkstra-Steiner algorithm and
establish a revisited algorithm, called DS*. The DS* algorithm allows for
arbitrary lower bounds as heuristics relaxing the previous condition on the
heuristic function. Notably, we can now use linear programming based lower
bounds. Further, we capture new requirements for a heuristic function in a
condition, which we call admissibility. We show that admissibility is indeed
weaker than consistency and establish correctness of the DS* algorithm when
using an admissible heuristic function. We implement DS* and combine it with
modern preprocessing, resulting in an open-source solver (DS* Solve). Finally,
we compare its performance on standard benchmarks and observe a competitive
behavior.
- Abstract（参考訳）: シュタイナー木問題は、ネットワーク設計、ルーティング、vlsi設計においてよく知られた問題である。
グラフ、エッジコスト、専用の頂点(終点)が与えられたとき、シュタイナーツリー問題は、最小コストですべての端末を接続するサブグラフを出力するように要求する。
動的計画法によってシュタイナー木問題を解決するための最先端のアルゴリズムはダイクストラ-シュタイナーアルゴリズムである。
このアルゴリズムは、端末のサブセットに基づいて小さなインスタンスを体系的に検索し、これらの小さなインスタンスにSteinerツリーを組み合わせることで、インスタンス全体のSteinerツリーを構築する。
検索は、検索空間を損なうために、導くヒューリスティックな機能に大きく依存している。
しかし、正確性を確保するため、このアルゴリズムは限定的なヒューリスティック関数、すなわちいわゆる一貫性条件を満たす関数のみを許容する。
本稿では,Dijkstra-Steinerアルゴリズムを強化し,DS*と呼ばれる再検討アルゴリズムを確立する。
DS*アルゴリズムは、ヒューリスティック関数の前の条件を緩和するヒューリスティックスとして任意の下界を許容する。
特に、線形プログラミングベースの下限が使えるようになりました。
さらに, 許容可能性と呼ばれる条件下でのヒューリスティック関数に対する新たな要件を捉えた。
そこで本研究では,DS*アルゴリズムの適合性は一貫性よりも弱いことを示し,許容ヒューリスティック関数を用いた場合の正当性を確立する。
我々はDS*を実装し、それを現代的な前処理と組み合わせることで、オープンソースソルバ(DS* Solve)を実現する。
最後に、標準ベンチマークのパフォーマンスを比較し、競争行動を観察する。
関連論文リスト
- LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳（メタデータ） (2024-06-29T05:14:04Z) - Query-decision Regression between Shortest Path and Minimum Steiner Tree [20.092639310758145]
本稿では,最短経路問題とSteiner木問題に焦点をあてる。
我々は、スコアリングモデルを構築するための実現可能な仮説空間の設計に関する理論的知見を提供する。
実験により,そのような問題を統計的に有意な程度に解決できることが示唆された。
論文 参考訳（メタデータ） (2024-02-03T17:05:01Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
ノードの集合が与えられるグラフ上のスタイナー木問題を考える。
目的は、追加ノードを含むすべてのノードを含むツリーのサブグラフを見つけることである。
論文 参考訳（メタデータ） (2022-08-25T10:31:00Z) - CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial
Optimization Problems [0.0]
本稿では、マルコフ連鎖からSAに基づく奥行き制限木への探索空間の拡大による探索アルゴリズムを提案する。
それぞれのイテレーションにおいて、このアルゴリズムは、先を見据えて、木に沿って探索することで、実現可能な探索空間内で最高の準最適解を選択する」。
以上の結果から,IsingのNP最適化問題に対する高次木探索戦略は,より少ないエポックの範囲で解決可能であることが示唆された。
論文 参考訳（メタデータ） (2022-03-09T10:07:26Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z) - Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved
Complexities [21.13934071954103]
本稿では,非インワンテキスト変数 Descent に対する決定論的アルゴリズムを提案する。
SGC仮定の下では,アルゴリズムの複雑さが既存のアルゴリズムの複雑さと一致していることが示される。
結果はオラクル・テキストZO-GDMSAで示され、数値実験により理論的結果が裏付けられる。
論文 参考訳（メタデータ） (2020-01-22T00:05:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。