@inproceedings{
eberle2024accelerating,
title={Accelerating Matroid Optimization through Fast Imprecise Oracles},
author={Franziska Eberle and Felix Hommelsheim and Alexander Lindermayr and Zhenwei Liu and Nicole Megow and Jens Schl{\"o}ter},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=0qb8KoPsej}
}
Querying complex models for precise information (e.g. traffic models, database systems, large ML models) often entails intense computations and results in long response times. Thus, weaker models which give imprecise results quickly can be advantageous, provided inaccuracies can be resolved using few queries to a stronger model. In the fundamental problem of computing a maximum-weight basis of a matroid, a well-known generalization of many combinatorial optimization problems, algorithms have access to a clean oracle to query matroid information. We additionally equip algorithms with a fast but dirty oracle. We design and analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle, while maintaining robustness against arbitrarily poor dirty oracles, approaching the performance of classic algorithms for the given problem. Notably, we prove that our algorithms are, in many respects, best-possible. Further, we outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.
Accelerating Matroid Optimization through Fast Imprecise Oracles
Franziska Eberle Felix Hommelsheim Alexander Lindermayr Zhenwei Liu Nicole Megow Jens Schlöter