論文の概要: Query-decision Regression between Shortest Path and Minimum Steiner Tree
- arxiv url: http://arxiv.org/abs/2402.02211v1
- Date: Sat, 3 Feb 2024 17:05:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-06 21:28:18.210932
- Title: Query-decision Regression between Shortest Path and Minimum Steiner Tree
- Title（参考訳）: 最短経路と最小ステイナツリー間のクエリ-決定回帰
- Authors: Guangmo Tong, Peng Zhao, Mina Samizadeh
- Abstract要約: 本稿では,最短経路問題とSteiner木問題に焦点をあてる。
我々は、スコアリングモデルを構築するための実現可能な仮説空間の設計に関する理論的知見を提供する。
実験により,そのような問題を統計的に有意な程度に解決できることが示唆された。
- 参考スコア（独自算出の注目度）: 20.092639310758145
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Considering a graph with unknown weights, can we find the shortest path for a
pair of nodes if we know the minimal Steiner trees associated with some subset
of nodes? That is, with respect to a fixed latent decision-making system (e.g.,
a weighted graph), we seek to solve one optimization problem (e.g., the
shortest path problem) by leveraging information associated with another
optimization problem (e.g., the minimal Steiner tree problem). In this paper,
we study such a prototype problem called \textit{query-decision regression with
task shifts}, focusing on the shortest path problem and the minimum Steiner
tree problem. We provide theoretical insights regarding the design of
realizable hypothesis spaces for building scoring models, and present two
principled learning frameworks. Our experimental studies show that such
problems can be solved to a decent extent with statistical significance.
- Abstract（参考訳）: 未知重みを持つグラフを考えると、ノードのサブセットに関連する最小のスタイナー木を知っていれば、一対のノードの最も短いパスを見つけることができるだろうか?
すなわち、固定潜在意思決定システム(例えば、重み付きグラフ)に関して、別の最適化問題(例えば、最小シュタイナー木問題)に関連する情報を活用して、1つの最適化問題(例えば、最短経路問題)を解決しようとする。
本稿では,タスクシフトを用いた‘textit{query-decision regression’と呼ばれるプロトタイプ問題を,最短経路問題と最小スタイナーツリー問題に着目して検討する。
評価モデル構築のための実現可能な仮説空間の設計に関する理論的考察と、2つの原則的学習フレームワークを提案する。
実験により,このような問題は統計的意義をもってある程度解決できることが示された。
関連論文リスト
- Kernel Search approach to solve the Minimum Spanning Tree Problem with conflicting edge pairs [0.0]
本稿では,カーネルサーチ手法を用いて,最小スパンニング木問題と競合を解消する。
このアプローチの主な新規性は、アルゴリズム内でコンフリクトグラフの独立したセットを使用することである。
論文 参考訳（メタデータ） (2024-01-04T12:10:39Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - 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 Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
ノードの集合が与えられるグラフ上のスタイナー木問題を考える。
目的は、追加ノードを含むすべてのノードを含むツリーのサブグラフを見つけることである。
論文 参考訳（メタデータ） (2022-08-25T10:31:00Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文 参考訳（メタデータ） (2021-10-27T10:45:21Z) - Computing Steiner Trees using Graph Neural Networks [1.0159681653887238]
本稿では,スタイナーツリー問題に取り組む。
低コストのSteiner木を計算するために4つの学習フレームワークを使用します。
我々の発見は,従来の2-近似アルゴリズムよりもGNN手法のアウト・オブ・ボックス適用の方が悪いことを示唆している。
論文 参考訳（メタデータ） (2021-08-18T19:55:16Z) - Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
数学用語問題(mwps)の従来のニューラルネットワークソルバは、完全な監視によって学習され、多様なソリューションを生み出すことができない。
MWPを学習するためのテキスト弱教師付きパラダイムを提案する。
この手法は最終回答のアノテーションのみを必要とし、単一の問題に対して様々な解決策を生成できる。
論文 参考訳（メタデータ） (2020-12-19T03:10:21Z) - Solving the Steiner Tree Problem with few Terminals [8.024778381207128]
動的プログラミングによるスタイナーツリー問題の解法として、Dijkstra-Steinerアルゴリズムがある。
我々はDijkstra-Steinerアルゴリズムを強化し、DS*と呼ばれる再検討アルゴリズムを確立する。
そこで本研究では,DS* アルゴリズムの適合性は整合性よりも弱いことを示し,許容関数を用いた場合の正当性を確立する。
論文 参考訳（メタデータ） (2020-11-09T17:46:02Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。