論文の概要: Learning-Augmented Algorithms for Online Steiner Tree

• arxiv url: http://arxiv.org/abs/2112.05353v2
• Date: Sat, 18 Mar 2023 12:33:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-24 05:30:52.593417
• Title: Learning-Augmented Algorithms for Online Steiner Tree
• Title（参考訳）: オンラインステイナツリーのための学習強化アルゴリズム
• Authors: Chenyang Xu and Benjamin Moseley
• Abstract要約: 本稿では,どの端末がオンラインにやってくるかを予測するアルゴリズムについて考察する。 予測は誤りであり、アルゴリズムのパフォーマンスは誤って予測された端末の数によってパラメータ化される。 新たなオンラインアルゴリズムは,適度に正確な予測でも高い性能を示す。
• 参考スコア（独自算出の注目度）: 14.506230077020994
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm's worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms' performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.
• Abstract（参考訳）: 本稿では,機械学習予測とオンラインアルゴリズム設計を統合したアルゴリズム解析モデルについて考察する。 このモデルでは、有向グラフおよび無向グラフのオンラインSteiner木問題を考える。 シュタイナーツリーは、オンライン設定において強い境界を持つことが知られており、アルゴリズムの最悪の保証は望ましくない。 本稿では,どの端末がオンラインに到着するかを予測するアルゴリズムについて検討する。 予測は誤りであり、アルゴリズムのパフォーマンスは誤って予測された端末の数によってパラメータ化される。 これらの保証は、アルゴリズムが良い予測でオンラインの下限を突破し、予測エラーが大きくなるにつれて競争比率が優雅に低下することを保証する。 そして、この理論が経験的に何が起こるかを予測する。 分布から端末が引き出されるグラフ上で、新しいオンラインアルゴリズムは、適度に正確な予測であっても、高い性能を示す。

関連論文リスト

• Improving Online Algorithms via ML Predictions [19.03466073202238]
  我々は,スキーレンタルと非好ましくないジョブスケジューリングの2つの古典的問題を考察し,予測を用いて意思決定を行う新しいオンラインアルゴリズムを得る。 これらのアルゴリズムは予測器の性能を損なうものであり、より良い予測で改善するが、予測が貧弱な場合はあまり劣化しない。
  論文  参考訳（メタデータ） (2024-07-25T02:17:53Z)
• Competitive Algorithms for Online Knapsack with Succinct Predictions [16.793099279933163]
  オンラインのknapsack問題では、異なる値と重みを持つオンラインで到着するアイテムをキャパシティ限定のknapsackにまとめて、受け入れられたアイテムの総価値を最大化する。 この問題に対するテキスト学習強化アルゴリズムについて検討し、機械学習による予測を用いて悲観的な最悪のケースの保証を超えて行動することを目的とする。
  論文  参考訳（メタデータ） (2024-06-26T20:38:00Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
  論文  参考訳（メタデータ） (2022-05-25T15:24:03Z)
• Online Algorithms with Multiple Predictions [17.803569868141647]
  本稿では,複数の機械学習予測を付加したオンラインアルゴリズムについて検討する。 我々のアルゴリズムは、オンラインアルゴリズムの古典的ポテンシャルに基づく分析に予測の利用を取り入れている。
  論文  参考訳（メタデータ） (2022-05-08T17:33:01Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Online Paging with a Vanishing Regret [6.520803851931362]
  本稿では,オンラインアルゴリズムが複数の予測器にアクセスでき,ページ到着時刻の予測列を生成するオンラインページング問題の変種について考察する。 予測器は時折予測誤差を発生させ、そのうちの少なくとも1つが予測誤差のサブ線形数を生成すると仮定する。 この仮定は、最適オフラインアルゴリズムに対する時間平均後悔が無限大になる傾向にあるランダム化オンラインアルゴリズムの設計に十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-18T18:17:49Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。