A universal error measure for input predictions applied to online graph problems

We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a general template which we apply to online graph problems. The measure captures errors due to absent predicted requests as well as unpredicted actual requests; hence, predicted and actual inputs can be of arbitrary size. We achieve refined performance guarantees for previously studied network design problems in the online-list model, such as Steiner tree and facility location. Further, we initiate the study of learning-augmented algorithms for online routing problems, such as the online traveling salesperson problem and the online dial-a-ride problem, where (transportation) requests arrive over time (online-time model). We provide a general algorithmic framework and we give error-dependent performance bounds that improve upon known worst-case barriers, when given accurate predictions, at the cost of slightly increased worst-case bounds when given predictions of arbitrary quality.

• View at Publisher
• View at arXiv

Free Full Text ( Final Version , 2mb )

See Also
inProceedings A universal error measure for input predictions applied to online graph problems G. Bernardini (Giulia), A. Lindermayr (Alexander), A. Marchetti Spaccamela (Alberto), N. Megow (Nicole), L. Stougie (Leen) and M.J.M. Sweering (Michelle)