The ordered \(k\)-median problem: surrogate models and approximation algorithms (Q2316614)

For the first time a provably-good polynomial approximation algorithm is presented for the following metric discrete convex ordered \(k\)-median problem: on a metric \(n\)-point space find a \(k\)-subset which minimizes the (nonincreasingly) weighted sum of all nonincreasingly reordered point-to-subset closest distances. Given some desired approximation level \(\epsilon\), the approach is roughly as follows. Under a polynomial number of hypotheses, to be tested a posteriori each in turn, surrogate objectives of standard unordered \(k\)-median type are constructed having proven approximate optimal value. In the case of a general metric these surrogate objectives are further smoothed, on which a single-swap local search method is applied, yielding a solution proved to be within a \(O(\log n)\) factor of the original optimal value. For a tree metric, a binary edge-weighted tree representation allows for a dynamic programming approach to solve the surrogate to optimality, which is proved to yield a factor \(2+\epsilon\) optimal solution to the original problem. The construction of tree metrics whose surrogates have an optimality gap of \(2-O(\epsilon)\) shows this latter is essentially tight.