An explore-exploit algorithm achieves O(OPT^{2/3}) regret when combining multiple MTS heuristics with bandit access, and this is tight up to log factors.
A Universal Error Measure for Input Predictions Applied to Online Graph Problems
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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.
fields
cs.LG 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors
An explore-exploit algorithm achieves O(OPT^{2/3}) regret when combining multiple MTS heuristics with bandit access, and this is tight up to log factors.