The ordered k-median problem: surrogate models and approximation algorithms

Aouad, A and Segev, D (2019) The ordered k-median problem: surrogate models and approximation algorithms. Mathematical Programming, 177 (1-2). pp. 55-83. ISSN 0025-5610 OPEN ACCESS


In the last two decades, 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(logn) -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.

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Date Deposited: 21 Feb 2019 14:24
Date of first compliant deposit: 20 Feb 2019
Subjects: Algorithms
Last Modified: 30 Sep 2023 00:37

Export and Share


Accepted Version - Text


View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item