Home » Publication » 27206

Dettaglio pubblicazione

2022, Advances in Neural Information Processing Systems, Pages - (volume: 35)

A universal error measure for input predictions applied to online graph problems (04b Atto di convegno in volume)

Iulia Bernardini, Alexander Lindermayr, MARCHETTI SPACCAMELA Alberto, Nicole Megow, Leen Stougie, Michelle Sweering

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.
ISBN: 9781713871088
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma