Constant-factor approximation for ordered k-median

This is the authors' abstract. We don't add key points for this paper.

We study the Ordered k-Median problem, in which the solution is evaluated by first sorting the client connection costs and then multiplying them with a predefined non-increasing weight vector (higher connection costs are taken with larger weights). Since the 1990s, this problem has been studied extensively in the discrete optimization and operations research communities and has emerged as a framework unifying many fundamental clustering and location problems such as k-Median and k-Center. Obtaining non-trivial approximation algorithms was an open problem even for simple topologies such as trees. Recently, Aouad and Segev (2017) were able to obtain an O(log n) approximation algorithm for Ordered k-Median using a sophisticated local-search approach. The existence of a constant-factor approximation algorithm, however, remained open even for the rectangular weight vector.