Approximation algorithms for geometric median problems
From MaRDI portal
Publication:1209349
DOI10.1016/0020-0190(92)90208-DzbMath0764.68079OpenAlexW2102815056MaRDI QIDQ1209349
Jyh-Han Lin, Jeffrey Scott Vitter
Publication date: 16 May 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(92)90208-d
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (27)
An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution ⋮ Clustering to minimize the sum of cluster diameters ⋮ Cluster editing problem for points on the real line: a polynomial time algorithm ⋮ \(k\)-median: exact recovery in the extended stochastic ball model ⋮ Approximation algorithms for the fault-tolerant facility location problem with penalties ⋮ Approximation algorithms for the fault-tolerant facility location problem with submodular penalties ⋮ An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions ⋮ Approximation algorithms for median hub location problems ⋮ Constant-factor approximation algorithms for some maximin multi-clustering problems ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ Cache placement in sensor networks under an update cost constraint ⋮ A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem ⋮ Local search algorithms for the red-blue median problem ⋮ Incremental medians via online bidding ⋮ Facility location models for distribution system design ⋮ A Lagrangean heuristic for the plant location problem with multiple facilities in the same site ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Approximating $k$-Median via Pseudo-Approximation ⋮ K-center and K-median problems in graded distances ⋮ Joint object placement and node dimensioning for internet content distribution ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ An LP rounding algorithm for approximating uncapacitated facility location problem with penalties ⋮ Facility Location with Matroid or Knapsack Constraints ⋮ Unnamed Item ⋮ An approximation algorithm for the maximization version of the two level uncapacitated facility location problem ⋮ A constant-factor approximation algorithm for the \(k\)-median problem
Cites Work
- A new polynomial-time algorithm for linear programming
- Clustering to minimize the maximum intercluster distance
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Unnamed Item
This page was built for publication: Approximation algorithms for geometric median problems
