Abstract
We study a natural generalization of the celebrated ordered kmedian problem, named robust ordered kmedian, also known as ordered kmedian with outliers. We are given facilities ℱ and clients ? in a metric space (ℱ∪?,d), parameters k,m ∈ ℤ_+ and a nonincreasing nonnegative 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 nonincreasingly sorted version of c. Robust ordered kmedian captures many interesting clustering problems recently studied in the literature, e.g., robust kmedian, ordered kmedian, etc.
We obtain the first polynomialtime constantfactor approximation algorithm for robust ordered kmedian, 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 kmedian. This appears to invalidate previous methods in approximating the highly nonlinear ordered objective. To overcome this issue, we introduce a novel yet very simple reduction framework that enables linear analysis of the nonlinear objective. We also devise the first constantfactor approximations for ordered matroid median and ordered knapsack median using the same framework, and the approximation factors are 19.8 and 41.6, respectively.
BibTeX  Entry
@InProceedings{deng_et_al:LIPIcs.APPROX/RANDOM.2022.34,
author = {Deng, Shichuan and Zhang, Qianfan},
title = {{Ordered kMedian with Outliers}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {34:134:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17156},
URN = {urn:nbn:de:0030drops171560},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.34},
annote = {Keywords: clustering, approximation algorithm, design and analysis of algorithms}
}
Keywords: 

clustering, approximation algorithm, design and analysis of algorithms 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) 
Issue Date: 

2022 
Date of publication: 

15.09.2022 