Motivated by applications in supply chain, network management, and machine learning, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. While antecedent literature has focused on mathematical properties of ordered median functions, integer programming methods, various heuristics, and special cases, this problem was not studied thus far through the lens of approximation algorithms. In particular, even on simple network topologies, such as trees or line graphs, obtaining non-trivial approximation guarantees is an open question. The main contribution of this paper is to devise the first provably-good approximation algorithms for the ordered k-median problem. We develop a novel approach that relies primarily on a surrogate model, where the ordered median function is replaced by a simplified ranking-invariant functional form, via efficient enumeration. Surprisingly, while this surrogate model is Ω(n Ω(1) )-hard to approximate on general metrics, we obtain an O(log n)approximation for our original problem by employing local search methods on a smooth variant of the surrogate function. In addition, an improved guarantee of 2 + is obtained on tree metrics by optimally solving the surrogate model through dynamic programming. Finally, we show that the latter optimality gap is tight up to an O( ) term. Motivated by applications in supply chain, network management, and machine learning [36, 35, 8, 38] , the ordered k-median problem has been developing in the last two decades as a robust and unified approach to facility location. In this setting, we are given a finite metric space (V, d) on n vertices, a sequence of penalty weights λ 1 ≥ · · · ≥ λ n ≥ 0, and an integer parameter k. For any set of facilities F ⊆ V , the ordered median cost function penalizes the distance d(v, F) of each vertex v ∈ V to its nearest facility by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. To formalize this criterion, for every ranking i ∈ [n], let ∆ F (i) be the i-th largest distance out of {d(v, F) : v ∈ V }, breaking ties arbitrarily. Then, the largest distance ∆ F (1) is penalized by λ 1 , the second largest distance ∆ F (2) is penalized by λ 2 , so forth and so on, ensuring that higher-ranked vertices are penalized more heavily than lower-ranked ones. Consequently, the objective is to compute a set F ⊆ V of at most k facilities that minimizes the ordered median cost function: Relation to basic models. The ordered median framework develops a uniform and standardized approach to a wide array of facility location problems, where the cost function is expressed in general form, applying arbitrary penalty weights depending on the percentile rank of the coverage distances. This modeling framework subsumes some of the most fundamental objective functions in location theory [11, 23, 3, 29, 9, 22, 48, 49] , such as: • k-median, which minimizes the average distance to the nearest facility, captured by setting (λ 1 , . . . , λ n ) = (1, . . . , 1). • k-center, which minimizes the maximal coverage distance, with (λ 1 , . . . , λ n ) = (1, 0, . . . , 0). • k-centdian, which generalizes convex combinations of k-median and k-center. • k-facility p-centrum, which minimizes the sum of the p-largest coverage distances, with λ 1 = · · · = λ p = 1 and λ p+1 = · · · = λ n = 0. In its utmost generality, the ordered median function allows one to formulate a continuum of trade-offs between the k-median and k-center models (see, for example, [37, Chap. 1]), where outlier vertices are penalized according to their percentile rank. For an in-depth discussion of the theory and applications of facility location models, we refer the reader to books on this general topic [34, 13] as well as to those dedicated specifically to ordered median models [27, 37] . Computational challenges. The modeling power discussed above poses additional technical obstacles, in comparison to specialized objectives such as k-median and k-center, which are known to admit constant-factor approximations [11, 23, 3, 29, 9, 22] . The first challenge stems from the dependency of the ordered median cost function on the relative distance rankings. For example, due to the lack of clear separability properties [45] , even on tree metrics or line graphs
The first provable approximation algorithm for Ordered k-Median was proposed by REF , and they gave 2-approximation for trees and O(log n)-approximation for general metrics.
The ordered k-median problem: surrogate models and approximation algorithms
Mathematical Programming
Computer Science Mathematics