論文の概要: Solving Large Steiner Tree Problems in Graphs for Cost-Efficient
Fiber-To-The-Home Network Expansion
- arxiv url: http://arxiv.org/abs/2109.10617v1
- Date: Wed, 22 Sep 2021 09:33:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-23 13:51:48.679168
- Title: Solving Large Steiner Tree Problems in Graphs for Cost-Efficient
Fiber-To-The-Home Network Expansion
- Title（参考訳）: コスト効率の良いファイバ・トゥ・ザ・ホームネットワーク拡張のためのグラフにおける大型スチナーツリー問題の解法
- Authors: Tobias M\"uller, Kyrill Schmid, Dani\"elle Schuman, Thomas Gabor,
Markus Friedrich, Marc Geitz
- Abstract要約: ファイバ・トゥ・ザ・ホーム(FTTH)ネットワークの拡大は、高価な発掘作業のために高いコストを発生させる。
この研究は、Quantum Annealing、Simulated Annealing、Evolutionary Algorithmsやslime-typeoldベースの最適化といった自然に着想を得た手法など、今後の技術について研究している。
- 参考スコア（独自算出の注目度）: 5.5955402258229405
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The expansion of Fiber-To-The-Home (FTTH) networks creates high costs due to
expensive excavation procedures. Optimizing the planning process and minimizing
the cost of the earth excavation work therefore lead to large savings.
Mathematically, the FTTH network problem can be described as a minimum Steiner
Tree problem. Even though the Steiner Tree problem has already been
investigated intensively in the last decades, it might be further optimized
with the help of new computing paradigms and emerging approaches. This work
studies upcoming technologies, such as Quantum Annealing, Simulated Annealing
and nature-inspired methods like Evolutionary Algorithms or slime-mold-based
optimization. Additionally, we investigate partitioning and simplifying
methods. Evaluated on several real-life problem instances, we could outperform
a traditional, widely-used baseline (NetworkX Approximate Solver) on most of
the domains. Prior partitioning of the initial graph and the presented
slime-mold-based approach were especially valuable for a cost-efficient
approximation. Quantum Annealing seems promising, but was limited by the number
of available qubits.
- Abstract（参考訳）: fiber-to-the-home (ftth)ネットワークの拡張は、高価な掘削手順によって高いコストを発生させる。
計画プロセスの最適化と地球掘削作業のコストの最小化により、大きな貯蓄がもたらされる。
数学的には、FTTHネットワーク問題は最小のSteiner Tree問題として記述できる。
Steiner Treeの問題はここ数十年ですでに徹底的に研究されているが、新しいコンピューティングパラダイムと新しいアプローチの助けを借りてさらに最適化されるかもしれない。
この研究は、量子アニーリング、シミュレートアニーリング、進化アルゴリズムやスライム・モールドに基づく最適化のような自然にインスパイアされた手法など、今後の技術を研究する。
さらに,分割と簡易化について検討する。
いくつかの実生活問題で評価すると、従来の広く使われているベースライン(ネットワークx近似解法)をほとんどのドメインで上回ることができる。
初期グラフと提示スライム型アプローチの事前分割は, コスト効率のよい近似法として特に有用であった。
Quantum Annealingは有望なようだが、利用可能な量子ビットの数によって制限された。
関連論文リスト
- The Complexity of Optimizing Atomic Congestion [14.845310803203724]
アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。
非常に単純なネットワークでも問題は非常に難解なままである。
我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
論文 参考訳（メタデータ） (2023-12-15T21:31:30Z) - 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) - Efficient Neural PDE-Solvers using Quantization Aware Training [71.0934372968972]
量子化は、性能を維持しながら推論の計算コストを下げることができることを示す。
4つの標準PDEデータセットと3つのネットワークアーキテクチャの結果、量子化対応のトレーニングは、設定と3桁のFLOPで機能することがわかった。
論文 参考訳（メタデータ） (2023-08-14T09:21:19Z) - Neural Quantile Optimization for Edge-Cloud Networking [13.509945075582447]
我々は,バースト可能な請求書に基づいて制約を満足し,コストを最小化するエッジ・クラウド・コンピューティング・ネットワークにおいて,最適なトラフィック割当方式を模索する。
本稿では,教師なし学習による最適化問題を解決するため,Gumbel-softmaxサンプリングネットワークを提案する。
トレーニングされたネットワークは、効率的なトラフィック割当スキームサンプリングとして機能し、実現可能性およびコスト関数値のランダム戦略を著しく上回る。
論文 参考訳（メタデータ） (2023-07-11T11:05:10Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree
Problems [0.0]
我々は,グラフ上の一般的な最適化問題に対して,決定過程(MDP)を定義することによって,様々な木にまたがる問題を解く新しいフレームワークであるNeuroPrimを提案する。
この枠組みをユークリッド空間上の3つの難しい問題に適用する: Degree-constrained Minimum Spanning Tree (DCMST) 問題、最小コストスパンニングツリー (MRCST) 問題、ルーティンググラフ (STP) におけるスタイナーツリー問題。
論文 参考訳（メタデータ） (2022-10-22T13:49:29Z) - Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted
Graph Convolutional Neural Networks [13.985534521589257]
グラフ畳み込みニューラルネットワーク(GNN)は、最適化の文脈で有望であることが証明されている。
我々は、グラフ畳み込みネットワーク、符号付きグラフ畳み込みネットワーク、グラフ等化ネットワークなど、さまざまなGNNに適応する。
エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。
論文 参考訳（メタデータ） (2022-04-04T10:21:02Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳（メタデータ） (2021-04-14T09:22:42Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳（メタデータ） (2021-02-16T06:04:27Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Computation Reduction in Bayesian Neural Networks Through
Feature Decomposition and Memorization [10.182119276564643]
本稿では,計算コストを削減するため,効率的なBNN推論フローを提案する。
計算の約半分は従来の手法と比べて取り除くことができる。
We implement our approach in Verilog and synthesise it with 45 $nm$ FreePDK technology。
論文 参考訳（メタデータ） (2020-05-08T05:03:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。