A Simple Combinatorial Algorithm for Robust Matroid Center

Georg Anegg, Laura Vargas Koch, Rico Zenklusen

Submitted on 7 November 2022


Recent progress on robust clustering led to constant-factor approximations for Robust Matroid Center. After a first combinatorial 7-approximation that is based on a matroid intersection approach, two tight LP-based 3-approximations were discovered, both relying on the Ellipsoid Method. In this paper, we show how a carefully designed, yet very simple, greedy selection algorithm gives a 5-approximation. An important ingredient of our approach is a well-chosen use of Rado matroids. This enables us to capture with a single matroid a relaxed version of the original matroid, which, as we show, is amenable to straightforward greedy selections.


Comment: To appear at SOSA 2023

Subjects: Computer Science - Data Structures and Algorithms; Mathematics - Optimization and Control; 90C27, 68W40, 68Q25; F.2