論文の概要: Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
- arxiv url: http://arxiv.org/abs/2602.24232v1
- Date: Fri, 27 Feb 2026 17:58:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-02 19:48:24.549811
- Title: Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
- Title（参考訳）: Metric Forest Completionによる学習強化スパンニング木アルゴリズムの改良
- Authors: Nate Veldt, Thomas Stanley, Benjamin W. Priest, Trevor Steil, Keita Iwabuchi, T. S. Jayram, Grace J. Li, Geoffrey Sanders,
- Abstract要約: 任意の距離空間の点に対する近似最小スパンニング木(MST)を求める学習拡張アルゴリズムを提案する。
分析の1つは、MFCが2.62ドル、MSTが2ドル、(2+1)$が2ドルから2ドルまで、前のアルゴリズムの近似係数を改善することである。
- 参考スコア（独自算出の注目度）: 8.063077447427451
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present improved learning-augmented algorithms for finding an approximate minimum spanning tree (MST) for points in an arbitrary metric space. Our work follows a recent framework called metric forest completion (MFC), where the learned input is a forest that must be given additional edges to form a full spanning tree. Veldt et al. (2025) showed that optimally completing the forest takes $Ω(n^2)$ time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a $(2γ+ 1)$-approximation for the original MST problem, where $γ\geq 1$ is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal $Ω(n^2)$-time MFC algorithm. Our approach considers only edges incident to a growing number of strategically chosen ``representative'' points. One corollary of our analysis is to improve the approximation factor of the previous algorithm from 2.62 for MFC and $(2γ+1)$ for metric MST to 2 and $2γ$ respectively. We prove this is tight for worst-case instances, but we still obtain better instance-specific approximations using our generalized method. We complement our theoretical results with a thorough experimental evaluation.
- Abstract（参考訳）: 任意の距離空間の点に対する近似最小スパンニング木(MST)を求める学習強化アルゴリズムを提案する。
我々の研究は、メートル法森林完成(MFC)と呼ばれる最近の枠組みに従っており、学習された入力は、完全な分布木を形成するために、追加のエッジを与える必要がある森林である。
Veldt et al (2025) は森林を最適に完成させるのに Ω(n^2)$ かかることを示したが、MFCの2.62近似を設計した。
2γ+ 1)$-approximation for the original MST problem, where $γ\geq 1$ is a quality parameter for the initial forest。
このアルゴリズムと最適な$Ω(n^2)$-time MFCアルゴリズムを補間する一般化手法を提案する。
このアプローチでは,戦略的に選択された 'representative'' ポイントの数の増加に対して,エッジのみを考慮しています。
分析の結果,MFCは2.62ドル,MSTは2.γ+1ドル,MSTは2.γ$となっている。
最悪のケースではこれが厳密であることを示すが、一般化された手法を用いて、より優れたインスタンス固有近似が得られる。
我々は理論結果を徹底的な実験的評価で補完する。
関連論文リスト
- Precedence-Constrained Decision Trees and Coverings [0.8594140167290095]
この研究は、多くの最適化問題とそれらの間の還元的関係を考察する。
私たちが関心を持っている主な問題は、emph Optimal Decision TreeとemphSet Coverの2つです。
論文 参考訳（メタデータ） (2026-02-24T19:33:36Z) - Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。
無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。
本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
論文 参考訳（メタデータ） (2026-02-11T21:44:20Z) - Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees [7.2092555743847155]
任意の距離空間における$n$ポイントの最小スパンニングツリー(MST)を見つけることは、階層的クラスタリングや他の多くのMLタスクの基本的なプリミティブである。
まず,(1)実践的手法を用いて不連結成分の森を発見し,(2)森林の不連結成分を分布木に接続するためのエッジの小さな重み集合を見出した。
2番目のステップを最適に解くには、まだ$Omega(n2)$時間が必要ですが、サブクワッドラティックな2.62近似アルゴリズムを提供しています。
論文 参考訳（メタデータ） (2025-02-18T16:13:46Z) - Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳（メタデータ） (2024-02-21T15:06:51Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。
従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
論文 参考訳（メタデータ） (2023-05-22T19:59:19Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Unbiased and Efficient Sampling of Dependency Trees [0.0]
ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。
Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。
我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
論文 参考訳（メタデータ） (2022-05-25T09:57:28Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。