用机器学习预测请求位置，提升线上旅行维修工问题的求解效率。
Learning-Augmented Online TRP on a Line
- 基于预测位置设计确定性算法，完美预测下竞争力比为3.732。
- 预测有误差时，算法竞争力比最差不超过4，误差越大越接近4。
- 首次在学习增强框架下解决线性旅行维修工问题，适合在线调度研究者。
我们研究了在学习增强框架下的线上旅行维修工问题（Online TRP on a Line）。在原始模型中，请求沿直线随时间流式到达，目标是最小化请求完成时间之和或平均值。原始模型下最优确定性算法的竞争力比下界为 $1+ ext{√}2 > 2.414$，上界为4。本文提出预测模型：事先已知每个请求的位置预测（可能有误差），但到达时间未知。我们首先建立3-竞争力下界，该结果可推广至原始模型。随后设计一个确定性算法，在预测完美时达到 $(2+ ext{√}3) hickapprox 3.732$ 的竞争力比；当最大预测误差为 $δ>0$ 时，算法竞争力比为 $ ext{min}\{3.732+4δ,4\/}$，且已知 $δ$。据我们所知，这是首个在学习增强框架下针对线上旅行维修工问题的结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。