Online Combinatorial Linear Optimization via a Frank-Wolfe-Based Metarounding Algorithm

MITSUBOSHI Ryotaro, HATANO Kohei, TAKIMOTO Eiji

doi:10.48550/arxiv.2310.12629

Online Combinatorial Linear Optimization via a Frank-Wolfe-Based Metarounding Algorithm

DOI DOI Web Site 参考文献18件オープンアクセス

MITSUBOSHI Ryotaro

Department of Informatics, Kyushu University RIKEN AIP
HATANO Kohei

Department of Informatics, Kyushu University RIKEN AIP
TAKIMOTO Eiji

Department of Informatics, Kyushu University

この論文をさがす

CiNii Books

説明

<p>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.</p>