Metadata only
Date
2023Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
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. Show more
Publication status
publishedExternal links
Book title
2023 Symposium on Simplicity in Algorithms (SOSA)Pages / Article No.
Publisher
SIAMEvent
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Funding
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)
More
Show all metadata
ETH Bibliography
yes
Altmetrics