2026-07-25T22:06:54Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:17156 2024-03-06T10:59:07Z ddc:004 open_access
Ordered k-Median with Outliers Deng, Shichuan Zhang, Qianfan clustering approximation algorithm design and analysis of algorithms We study a natural generalization of the celebrated ordered k-median problem, named robust ordered k-median, also known as ordered k-median with outliers. We are given facilities β„± and clients π’ž in a metric space (β„±βˆͺπ’ž,d), parameters k,m ∈ β„€_+ and a non-increasing non-negative vector w ∈ ℝ_+^m. We seek to open k facilities F βŠ† β„± and serve m clients C βŠ† π’ž, inducing a service cost vector c = {d(j,F):j ∈ C}; the goal is to minimize the ordered objective w^⊀c^↓, where d(j,F) = min_{i ∈ F}d(j,i) is the minimum distance between client j and facilities in F, and c^↓ ∈ ℝ_+^m is the non-increasingly sorted version of c. Robust ordered k-median captures many interesting clustering problems recently studied in the literature, e.g., robust k-median, ordered k-median, etc. We obtain the first polynomial-time constant-factor approximation algorithm for robust ordered k-median, achieving an approximation guarantee of 127. The main difficulty comes from the presence of outliers, which already causes an unbounded integrality gap in the natural LP relaxation for robust k-median. This appears to invalidate previous methods in approximating the highly non-linear ordered objective. To overcome this issue, we introduce a novel yet very simple reduction framework that enables linear analysis of the non-linear objective. We also devise the first constant-factor approximations for ordered matroid median and ordered knapsack median using the same framework, and the approximation factors are 19.8 and 41.6, respectively. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Shichuan Deng and Qianfan Zhang 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.34 urn:nbn:de:0030-drops-171560 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.34 eng https://creativecommons.org/licenses/by/4.0/legalcode