論文の概要: Online TSP with Predictions

• arxiv url: http://arxiv.org/abs/2206.15364v1
• Date: Thu, 30 Jun 2022 15:35:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-01 15:57:54.319097
• Title: Online TSP with Predictions
• Title（参考訳）: オンラインTSPと予測
• Authors: Hsiao-Yu Hu, Hao-Ting Wei, Meng-Hsi Li, Kai-Min Chung and Chung-Shou Liao
• Abstract要約: 古典的オンライン旅行セールスマン問題(OLTSP)について検討する。 他の研究の予測モデルとは異なり、OLTSPの実際の要求はその到着時間と位置に関連しており、予測された要求と一致しないかもしれない。 我々の主な成果は、様々な予測モデルと設計アルゴリズムを研究し、異なる設定で最もよく知られた結果を改善することである。
• 参考スコア（独自算出の注目度）: 3.8411077568039866
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the study of online routing problems with predictions, inspired by recent exciting results in the area of learning-augmented algorithms. A learning-augmented online algorithm which incorporates predictions in a black-box manner to outperform existing algorithms if the predictions are accurate while otherwise maintaining theoretical guarantees even when the predictions are extremely erroneous is a popular framework for overcoming pessimistic worst-case competitive analysis. In this study, we particularly begin investigating the classical online traveling salesman problem (OLTSP), where future requests are augmented with predictions. Unlike the prediction models in other previous studies, each actual request in the OLTSP, associated with its arrival time and position, may not coincide with the predicted ones, which, as imagined, leads to a troublesome situation. Our main result is to study different prediction models and design algorithms to improve the best-known results in the different settings. Moreover, we generalize the proposed results to the online dial-a-ride problem.
• Abstract（参考訳）: 我々は,近年の学習支援アルゴリズムの領域におけるエキサイティングな結果に触発されて,予測を用いたオンラインルーティング問題の研究を開始する。 ブラックボックス方式で予測を組み込んだオンラインアルゴリズムは、予測が正確でありながら理論的な保証を保ちながら既存のアルゴリズムよりも優れており、悲観的な最悪ケースの競合分析を克服するための一般的なフレームワークである。 本研究では,特に従来のオンライン旅行セールスマン問題 (OLTSP) について検討し,今後の要求を予測によって拡張する。 他の研究の予測モデルとは異なり、OLTSPの実際の要求は到着時刻と位置と関連付けられており、予測された要求と一致しないかもしれない。 我々の主な成果は、様々な予測モデルと設計アルゴリズムを研究し、異なる設定で最もよく知られた結果を改善することである。 さらに,提案した結果をオンラインダイヤル・ア・ライド問題に一般化する。

関連論文リスト

• Improving Online Algorithms via ML Predictions [19.03466073202238]
  我々は,スキーレンタルと非好ましくないジョブスケジューリングの2つの古典的問題を考察し,予測を用いて意思決定を行う新しいオンラインアルゴリズムを得る。 これらのアルゴリズムは予測器の性能を損なうものであり、より良い予測で改善するが、予測が貧弱な場合はあまり劣化しない。
  論文  参考訳（メタデータ） (2024-07-25T02:17:53Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Online Algorithms with Uncertainty-Quantified Predictions [11.951228732915936]
  オンラインアルゴリズムの設計における不確実性定量化予測を最適に活用する問題について検討する。 特に,スキーレンタルとオンライン検索の2つの古典的オンライン問題について検討した。 我々は、UQ予測を完全に活用するために、アルゴリズム設計への非自明な修正が必要であることを実証する。
  論文  参考訳（メタデータ） (2023-10-17T20:09:41Z)
• 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)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Parsimonious Learning-Augmented Caching [29.975391787684966]
  本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。 定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
  論文  参考訳（メタデータ） (2022-02-09T03:40:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• 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)
• Counterfactual Predictions under Runtime Confounding [74.90756694584839]
  本研究は, 過去のデータからすべての関連要因を抽出した環境で, 事実予測タスクについて検討する。 本稿では,この環境下での対実予測モデル学習のための2次ロバスト手法を提案する。
  論文  参考訳（メタデータ） (2020-06-30T15:49:05Z)

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

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