直線上のオンライン巡回修理人問題に対する学習支援アルゴリズム
Learning-Augmented Online TRP on a Line
直線上のオンライン巡回修理人問題において、機械学習によるリクエスト位置の予測を活用する学習支援フレームワークを初めて適用し、予測が正確な場合に競合比2+√3を達成する決定論的アルゴリズムを提案した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Swapnil Guragain, Gokarna Sharma
分類: cs.DS, cs.RO
原文アブストラクト
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 $\delta > 0$), we show that our deterministic algorithm becomes $\min\{3.732+4\delta,4\}$-competitive, knowing $\delta$. To the best of our knowledge, these are the first results for online traveling repairperson problem in the learning-augmented framework.
