论文标题
适用于强大的矩形中心的简单组合算法
A Simple Combinatorial Algorithm for Robust Matroid Center
论文作者
论文摘要
鲁棒聚类的最新进展导致了稳健的矩形中心的恒定因子近似值。在基于Matroid交叉路口方法的第一个组合$ 7 $ - APPROXIMATION之后，发现了两个基于LP的$ 3 $ APPROXIMATIONS，都依赖于椭圆形方法。在本文中，我们展示了精心设计但又非常简单，贪婪的选择算法如何提供$ 5 $ approximation。我们方法的重要组成部分是对Rado Matroid进行了精心挑选的使用。这使我们能够使用单个曲霉捕获原始曲霉的轻松版本，正如我们所显示的，它可以正常贪婪的选择。
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.
