Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm
This work addresses the challenge of online optimization in combinatorial settings, offering a more efficient solution for applications like resource allocation, but it appears incremental as it builds on existing metarounding and approximation frameworks.
The paper tackles the problem of converting offline approximation algorithms for combinatorial linear optimization into efficient online algorithms, proposing a new Frank-Wolfe-based metarounding method that achieves significant improvements in both theoretical and practical efficiency.
Metarounding is an approach to convert an approximation algorithm for linear optimization over some combinatorial classes to an online linear optimization algorithm for the same class. We propose a new metarounding algorithm under a natural assumption that a relax-based approximation algorithm exists for the combinatorial class. Our algorithm is much more efficient in both theoretical and practical aspects.