論文の概要: Robustification of Online Graph Exploration Methods

• arxiv url: http://arxiv.org/abs/2112.05422v1
• Date: Fri, 10 Dec 2021 10:02:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-13 21:23:09.501796
• Title: Robustification of Online Graph Exploration Methods
• Title（参考訳）: オンライングラフ探索手法のロバスト化
• Authors: Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas N\"olke, Jens Schl\"oter
• Abstract要約: 我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 59.50307752165016
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. We initiate the study of a learning-augmented variant of the classical, notoriously hard online graph exploration problem by adding access to machine-learned predictions. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm and significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality. We provide theoretical worst-case bounds that gracefully degrade with the prediction error, and we complement them by computational experiments that confirm our results. Further, we extend our concept to a general framework to robustify algorithms. By interpolating carefully between a given algorithm and NN, we prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs.
• Abstract（参考訳）: 未知環境の探索は、ロボットナビゲーション、ネットワークセキュリティ、インターネット検索など、多くの領域における基本的なタスクである。 我々は、機械学習による予測へのアクセスを追加することで、古典的かつ悪名高いオンライングラフ探索問題の研究を開始する。 提案アルゴリズムは、予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合し、予測精度が高ければ既知のオンラインアルゴリズムを著しく上回り、予測品質が劣る場合には良好な保証を維持する。 予測誤差で優雅に劣化する理論的最悪ケース境界を提供し,結果を確認する計算実験によって補完する。 さらに、アルゴリズムを堅牢化するための汎用フレームワークまで、概念を拡張します。 与えられたアルゴリズムとnnを慎重に補間することにより、任意の入力に対する堅牢性を確立しつつ、特定の入力に対する個々の優れた性能を活用する新しい性能限界を証明できる。

関連論文リスト

• Competitive Algorithms for Online Knapsack with Succinct Predictions [16.793099279933163]
  オンラインのknapsack問題では、異なる値と重みを持つオンラインで到着するアイテムをキャパシティ限定のknapsackにまとめて、受け入れられたアイテムの総価値を最大化する。 この問題に対するテキスト学習強化アルゴリズムについて検討し、機械学習による予測を用いて悲観的な最悪のケースの保証を超えて行動することを目的とする。
  論文  参考訳（メタデータ） (2024-06-26T20:38:00Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Parsimonious Learning-Augmented Caching [29.975391787684966]
  本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。 定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
  論文  参考訳（メタデータ） (2022-02-09T03:40:11Z)
• Learning-Augmented Algorithms for Online Steiner Tree [14.506230077020994]
  本稿では,どの端末がオンラインにやってくるかを予測するアルゴリズムについて考察する。 予測は誤りであり、アルゴリズムのパフォーマンスは誤って予測された端末の数によってパラメータ化される。 新たなオンラインアルゴリズムは,適度に正確な予測でも高い性能を示す。
  論文  参考訳（メタデータ） (2021-12-10T06:18:19Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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