論文の概要: Learning-Augmented Online TRP on a Line

• arxiv url: http://arxiv.org/abs/2601.13494v1
• Date: Tue, 20 Jan 2026 01:10:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 08:17:40.854827
• Title: Learning-Augmented Online TRP on a Line
• Title（参考訳）: ライン上のオンラインTRPの学習
• Authors: Swapnil Guragain, Gokarna Sharma,
• Abstract要約: 本稿では,最近提案された学習強化フレームワーク内でのオンライン旅行修理担当者問題について考察する。 我々の予測モデルは、プリオリとして知られるストリーム内の各リクエストの予測位置、おそらくエラーを起こします。 我々の決定論的アルゴリズムは$min3.732+4,4$-competitiveとなり、$$を知ります。
• 参考スコア（独自算出の注目度）: 0.7677431882779153
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the online traveling repairperson problem on a line within the recently proposed learning-augmented framework, which provides predictions on the requests to be served via machine learning. In the original model (with no predictions), there is a stream of requests released over time along the line. The goal is to minimize the sum (or average) of the completion times of the requests. In the original model, the state-of-the-art competitive ratio lower bound is $1+\sqrt{2} > 2.414$ for any deterministic algorithm and the state-of-the-art competitive ratio upper bound is 4 for a deterministic algorithm. Our prediction model involves predicted positions, possibly error-prone, of each request in the stream known a priori but the arrival times of requests are not known until their arrival. We first establish a 3-competitive lower bound which extends to the original model. We then design a deterministic algorithm that is $(2+\sqrt{3})\approx 3.732$-competitive when predictions are perfect. With imperfect predictions (maximum error $δ> 0$), we show that our deterministic algorithm becomes $\min\{3.732+4δ,4\}$-competitive, knowing $δ$. To the best of our knowledge, these are the first results for online traveling repairperson problem in the learning-augmented framework.
• Abstract（参考訳）: 我々は,最近提案された学習強化フレームワークのライン上にオンラインの旅行修理担当者の問題を調査し,機械学習による要求の予測を行う。 オリジナルのモデルでは(予測なしで)、ラインに沿って時間をかけてリリースされるリクエストのストリームがあります。 目標は、リクエストの完了時間の総和(または平均)を最小化することです。 元のモデルでは、最先端競争比の下限は任意の決定論的アルゴリズムに対して1+\sqrt{2} > 2.414$であり、最先端競争比上限は決定論的アルゴリズムに対して4である。 我々の予測モデルは、プリオリとして知られるストリーム内の各リクエストの予測位置、おそらくエラーの発生率を含むが、そのリクエストの到着時刻は、到着するまで不明である。 まず、元のモデルに拡張する3つの競合的下界を確立する。 次に,予測が完全であれば2+\sqrt{3})\approx 3.732$-competitiveという決定論的アルゴリズムを設計する。 不完全予測(最大誤差$δ> 0$)では、決定論的アルゴリズムが$δ$を知り、$\min\{3.732+4δ,4\}$-competitiveとなることを示す。 我々の知る限りでは、これらは学習強化フレームワークにおけるオンラインの旅行修理担当者問題の最初の結果である。

関連論文リスト

• Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model [16.466711636334587]
  オンライン意思決定者は、到着や要求など、将来の変数に関する予測を得ることが多い。 意思決定者にとって予測精度は未知であるため、予測に盲目的に追従することは有害である。 我々は未知の予測精度に頑健な方法で予測を利用するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-21T04:57:32Z)
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions [19.537289123577022]
  有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2024-01-02T07:46:33Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Learning-Augmented Algorithms for Online TSP on the Line [4.636538620253008]
  本研究では,オンライントラベリングセールスマン問題 (TSP) を,機械学習による予測を付加した線上で研究する。 古典的な問題では、実際の行に沿って時間をかけてリリースされるリクエストのストリームがあります。 オープンな変種とクローズドな変種を区別し、全ての要求を処理した後、アルゴリズムに元の値を返すように要求する。
  論文  参考訳（メタデータ） (2022-06-01T17:47:26Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
  論文  参考訳（メタデータ） (2022-05-25T15:24:03Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。 目標は、予測を処理し、最小コストで予測を行うことです。 アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
  論文  参考訳（メタデータ） (2022-04-21T01:22:18Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。 本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
  論文  参考訳（メタデータ） (2022-02-07T21:08:02Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。 我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
  論文  参考訳（メタデータ） (2020-12-17T04:56:51Z)

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

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