論文の概要: Learning-Augmented Algorithms for Online Vertex Cover
- arxiv url: http://arxiv.org/abs/2606.22831v1
- Date: Mon, 22 Jun 2026 04:14:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-25 04:19:20.060381
- Title: Learning-Augmented Algorithms for Online Vertex Cover
- Title（参考訳）: オンライン頂点被覆のための学習強化アルゴリズム
- Authors: Tianhang Lu, Runtian Ren, Shengcai Liu,
- Abstract要約: 両部グラフと一般グラフの2つのグラフケースを考察する。
これらの問題は、学習強化スキーレンタルと同じ堅牢性-一貫性のトレードオフを許容していることが示される。
- 参考スコア（独自算出の注目度）: 2.162745596012608
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies learning-augmented online weighted vertex cover with advice and a parameter $λ\in (0,1)$. We consider two graph cases: bipartite graphs and general graphs. In both settings, the online algorithm must maintain a feasible vertex cover under irrevocable decisions. We show that these problems admit the same robustness--consistency tradeoffs as learning-augmented ski rental. For the bipartite graph model, we give a randomized algorithm that is $\frac{1}{1-e^{-λ}}$-robust and $\fracλ{1-e^{-λ}}$-consistent. For the general graph model, we give a deterministic algorithm that is $(1+\frac{1}λ)$-robust and $(1+λ)$-consistent. We prove that the tradeoffs above are optimal in both settings. We also validate the proposed algorithms through experiments on synthetic and real-world datasets.
- Abstract（参考訳）: 本稿では,学習支援型オンライン重み付き頂点カバーのアドバイスとパラメータ$λ\in (0,1)$について検討する。
両部グラフと一般グラフの2つのグラフケースを考察する。
どちらの設定でも、オンラインアルゴリズムは、望ましくない決定の下で、実現可能な頂点被覆を維持する必要がある。
これらの問題は、学習強化スキーレンタルと同じ堅牢性-一貫性のトレードオフを許容していることが示される。
二部グラフモデルに対しては、$\frac{1}{1-e^{-λ}}$-robust と $\fracλ{1-e^{-λ}}$-consistent というランダム化アルゴリズムを与える。
一般グラフモデルに対しては、$(1+\frac{1}λ)$-robust と$(1+λ)$-consistent という決定論的アルゴリズムを与える。
上記のトレードオフが両方の設定で最適であることを証明する。
また,合成および実世界のデータセットを用いた実験により,提案アルゴリズムの有効性を検証した。
関連論文リスト
- Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence [0.0]
隠れた$d$正規基底グラフを識別するための量子アルゴリズムを、その難解バージョンへのアクセスから$n$頂点に$G$を与える。
我々のアルゴリズムは概念的には単純で、$G_rm spire$ 上で連続時間ウォークし、古典的には pret*$ で 1 つのアダマールテストを行う。
論文 参考訳（メタデータ） (2026-05-11T20:44:32Z) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。
本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。