# Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm

arXiv: https://arxiv.org/abs/2310.12629 · HTML: https://mlsanity.com/paper/2310.12629/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 31 references that are in the map.
- First posted on arXiv 19 Oct 2023.

## Builds on (most cited first, 4 of 4)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Boosting as Frank-Wolfe](https://mlsanity.com/paper/2209.10831/) (2022)

## Abstract (arXiv)

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.