The ordered k-median problem: surrogate models and approximation algorithms
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.
- Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
- Constant-factor approximation for ordered k-median
- Multifacility ordered median problems on networks: A further analysis
- Approximation Algorithms for the k-Median Problem
- Approximating k-median via pseudo-approximation
- A Best Possible Heuristic for the k-Center Problem
- A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A modified variable neighborhood search for the discrete ordered median problem
- A new greedy approach for facility location problems
- A polynomial algorithm for thep-centdian problem on a tree
- A specialized branch \& bound \& cut for single-allocation ordered median hub location problems
- A threshold of ln n for approximating set cover
- A tight bound on approximating arbitrary metrics by tree metrics
- Algorithmic results for ordered median problems
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- An inverse approach to convex ordered median problems in trees
- Analysis of a Local Search Heuristic for Facility Location Problems
- Approximating k-median via pseudo-approximation
- Approximation algorithms for geometric median problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Constant-factor approximation for ordered k-median
- Constructing a DC decomposition for ordered median problems
- Convex ordered median problem with \(\ell _p\)-norms
- Easy and hard bottleneck location problems
- Exact procedures for solving the discrete ordered median problem
- Genetic algorithms for solving the discrete ordered median problem
- Geometrical properties of the symmetrical single facility location problem
- Greedy minimization of weakly supermodular set functions
- Heuristic procedures for solving the discrete ordered median problem
- scientific article; zbMATH DE number 44281 (Why is no real title available?)
- scientific article; zbMATH DE number 1746287 (Why is no real title available?)
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- scientific article; zbMATH DE number 1859298 (Why is no real title available?)
- scientific article; zbMATH DE number 1394671 (Why is no real title available?)
- Improved Combinatorial Algorithms for Facility Location Problems
- Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
- Least quantile regression via modern optimization
- Local Search Heuristics for k-Median and Facility Location Problems
- Locating hyperplanes to fitting set of points: a general framework
- Locating tree-shaped facilities using the ordered median objective
- Location science
- Location theory. A unified approach
- Lower-Stretch Spanning Trees
- Mathematical Programming for Data Mining: Formulations and Challenges
- Maximum gradient embeddings and monotone clustering
- Minimax regret single-facility ordered median location problems on networks
- Multifacility ordered median problems on networks: A further analysis
- On the computational complexity of centers locating in a graph
- On the exponential cardinality of FDS for the ordered p-median problem
- Ordered weighted average optimization in multiobjective spanning tree problem
- Revisiting k-sum optimization
- Robust discrete optimization and network flows
- Single-allocation ordered median hub location problems
- Solving the ordered one-median problem in the plane
- The k-centrum multi-facility location problem
- The \(p\)-facility ordered median problem on networks
- The ordered median Euclidean straight-line location problem
- A branch-and-price approach for the continuous multifacility monotone ordered median problem
- Approximation algorithms for clustering with dynamic points
- A fresh view on the discrete ordered median problem based on partial monotonicity
- Reverse greedy is bad for \(k\)-center
- Segmentation of scanning-transmission electron microscopy images using the ordered median problem
- Interpolating between \(k\)-median and \(k\)-center: approximation algorithms for ordered \(k\)-median
- Constant-factor approximation for ordered k-median
- Approximation algorithms for clustering with dynamic points
- Constraint relaxation for the discrete ordered median problem
- Tight approximation algorithms for ordered covering
- A robust ordered weighted averaging loss model for portfolio optimization
- A local search algorithm for radius-constrained k-median
- A local search algorithm for the radius-constrained k-median problem
- A parameterized approximation algorithm for the diversity-aware l-centrum problem
- New results on a general class of minimum norm optimization problems
This page was built for publication: The ordered \(k\)-median problem: surrogate models and approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2316614)
