論文の概要: A Universal Error Measure for Input Predictions Applied to Online Graph Problems

• arxiv url: http://arxiv.org/abs/2205.12850v1
• Date: Wed, 25 May 2022 15:24:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-26 17:51:33.816610
• Title: A Universal Error Measure for Input Predictions Applied to Online Graph Problems
• Title（参考訳）: オンライングラフ問題に適用した入力予測の普遍的誤差測定
• Authors: Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, Michelle Sweering
• Abstract要約: 本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
• 参考スコア（独自算出の注目度）: 57.58926849872494
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a general template which we apply to online graph problems. The measure captures errors due to absent predicted requests as well as unpredicted actual requests; hence, predicted and actual inputs can be of arbitrary size. We achieve refined performance guarantees for previously studied network design problems in the online-list model, such as Steiner tree and facility location. Further, we initiate the study of learning-augmented algorithms for online routing problems, such as the traveling salesperson problem and dial-a-ride problem, where (transportation) requests arrive over time (online-time model). We provide a general algorithmic framework and we give error-dependent performance bounds that improve upon known worst-case barriers, when given accurate predictions, at the cost of slightly increased worst-case bounds when given predictions of arbitrary quality.
• Abstract（参考訳）: 入力予測における誤差を定量化する新しい尺度を提案する。 この誤差は、最適に定義されたハイパーグラフの最小コストのハイパーエッジカバーに基づいており、オンライングラフ問題に適用する一般的なテンプレートを提供する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャするので、予測と実際の入力は任意のサイズにすることができる。 我々は,Steiner ツリーや施設位置などのオンラインリストモデルにおいて,これまで研究されてきたネットワーク設計問題に対して,洗練された性能保証を実現する。 さらに,旅行セールスマン問題やダイヤル・ア・ライド問題などのオンラインルーティング問題に対する学習提示アルゴリズムの研究を開始し,そこでは(移動)要求が時間とともに到着する(オンライン時間モデル)。 我々は一般的なアルゴリズムフレームワークを提供し、任意の品質の予測が与えられた場合、最悪のケース境界をわずかに増加させるコストで、既知の最悪のケース障壁を改善するエラー依存の性能境界を与える。

関連論文リスト

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Online Dynamic Acknowledgement with Learned Predictions [13.821981661594844]
  オンラインの動的認知問題を再考する。 問題の目標は、総要求遅延と承認コストを最小化することです。 このエレガントなモデルは、承認コストとリクエストで経験した待ち時間のトレードオフを研究します。
  論文  参考訳（メタデータ） (2023-05-25T20:05:47Z)
• Improved Online Conformal Prediction via Strongly Adaptive Online Learning [86.4346936885507]
  我々は、強い適応的後悔を最小限に抑える新しいオンライン共形予測手法を開発した。 提案手法は,すべての区間において,ほぼ最適に適応的な後悔を同時に達成できることを実証する。 実験により,本手法は実世界のタスクにおける既存の手法よりも,より優れたカバレッジと予測セットが得られることがわかった。
  論文  参考訳（メタデータ） (2023-02-15T18:59:30Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• 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)
• Backward-Compatible Prediction Updates: A Probabilistic Approach [12.049279991559091]
  本稿では,予測更新問題を定式化し,上記の質問に対する効率的な確率的アプローチを提案する。 標準分類ベンチマークデータセットの広範な実験において,提案手法は後方互換性のある予測更新のための代替戦略よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-07-02T13:05:31Z)
• Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing [12.961453245099044]
  本稿では,アルゴリズムが形式的に学習可能で,例えば頑健であることを要求して,予測を伴うアルゴリズムの拡張モデルを提案する。 ネットワークフロー割当問題と制限された割当ミスパン最小化の予測を含むオンラインアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-11-23T21:38:57Z)

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

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