論文の概要: Learning-Augmented Algorithms for Online TSP on the Line

• arxiv url: http://arxiv.org/abs/2206.00655v1
• Date: Wed, 1 Jun 2022 17:47:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-02 13:43:29.091298
• Title: Learning-Augmented Algorithms for Online TSP on the Line
• Title（参考訳）: オンラインTSPにおけるライン上の学習強化アルゴリズム
• Authors: Themis Gouleakis, Konstantinos Lakis and Golnoosh Shahkarami
• Abstract要約: 本研究では,オンライントラベリングセールスマン問題 (TSP) を,機械学習による予測を付加した線上で研究する。 古典的な問題では、実際の行に沿って時間をかけてリリースされるリクエストのストリームがあります。 オープンな変種とクローズドな変種を区別し、全ての要求を処理した後、アルゴリズムに元の値を返すように要求する。
• 参考スコア（独自算出の注目度）: 4.636538620253008
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the online Traveling Salesman Problem (TSP) on the line augmented with machine-learned predictions. In the classical problem, there is a stream of requests released over time along the real line. The goal is to minimize the makespan of the algorithm. We distinguish between the open variant and the closed one, in which we additionally require the algorithm to return to the origin after serving all requests. The state of the art is a $1.64$-competitive algorithm and a $2.04$-competitive algorithm for the closed and open variants, respectively \cite{Bjelde:1.64}. In both cases, a tight lower bound is known \cite{Ausiello:1.75, Bjelde:1.64}. In both variants, our primary prediction model involves predicted positions of the requests. We introduce algorithms that (i) obtain a tight 1.5 competitive ratio for the closed variant and a 1.66 competitive ratio for the open variant in the case of perfect predictions, (ii) are robust against unbounded prediction error, and (iii) are smooth, i.e., their performance degrades gracefully as the prediction error increases. Moreover, we further investigate the learning-augmented setting in the open variant by additionally considering a prediction for the last request served by the optimal offline algorithm. Our algorithm for this enhanced setting obtains a 1.33 competitive ratio with perfect predictions while also being smooth and robust, beating the lower bound of 1.44 we show for our original prediction setting for the open variant. Also, we provide a lower bound of 1.25 for this enhanced setting.
• Abstract（参考訳）: 本研究では,オンライントラベリングセールスマン問題 (TSP) を,機械学習による予測を付加した線上で研究する。 古典的な問題では、実際の行に沿って時間をかけてリリースされるリクエストのストリームがあります。 目標はアルゴリズムのメイズパンを最小化することである。 オープンな変種とクローズドな変種を区別し、全ての要求を処理した後、アルゴリズムに元の値を返すように要求する。 美術品の状態は、1.64$-competitiveアルゴリズムと2.04$-competitiveアルゴリズムであり、それぞれ閉変量と開変量に対してそれぞれ \cite{Bjelde:1.64} である。 どちらの場合も、厳密な下界は \cite{Ausiello:1.75, Bjelde:1.64} として知られている。 どちらの変種でも、我々の主予測モデルは要求の予測位置を含む。 アルゴリズムを導入する i) 閉変量に対する厳密な1.5の競争比と完全予測の場合の開変量に対する1.66の競争比を得る。 (ii)非有界予測誤差に対して頑健であり、 (iii) 予測誤差が増加するにつれて、その性能は優雅に低下する。 さらに, 最適オフラインアルゴリズムによる最終要求の予測を考慮し, オープン変種における学習提示設定をさらに検討した。 この拡張された設定に対するアルゴリズムは、完全な予測を伴う 1.33 の競合比を得ると同時に、滑らかで頑健であり、開変量に対する元の予測設定に対して示される 1.44 の低い境界を破る。 また、この強化された設定に対して、下限の 1.25 も提供します。

関連論文リスト

• Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
  本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。 我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
  論文  参考訳（メタデータ） (2023-05-16T07:52:08Z)
• Mixing predictions for online metric algorithms [34.849039387367455]
  我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。 我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。 我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
  論文  参考訳（メタデータ） (2023-04-04T13:18:00Z)
• 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)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。 本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
  論文  参考訳（メタデータ） (2022-02-07T21:08:02Z)
• 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)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)
• Online Page Migration with ML Advice [26.929268665630342]
  提案手法は,エムページマイグレーション問題に対するオンラインアルゴリズムで,予測が不完全である可能性があり,その性能向上を図っている。 アルゴリズムが入力シーケンスの予測を与えられると、競合比が1ドルになることを示す。 我々の成果は、機械学習を使って古典的なアルゴリズムの性能を向上させる、最近の仕事の本体に追加される。
  論文  参考訳（メタデータ） (2020-06-09T03:15:34Z)

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

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