Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation

DOI10.1145/375827.375845zbMath1089.68665OpenAlexW2139841919MaRDI QIDQ4406291

Ka Wong Chong, Yijie Han, Tak-Wah Lam

Publication date: 25 June 2003

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/375827.375845

zbMATH Keywords

parallel algorithm minimum spanning tree problem exclusive-read exclusive-write parallel random access machine

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (26)

Clustering with or without the approximation ⋮ On the parallel computation of the biconnected and strongly connected co-components of graphs ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Improved parameterized approximation for balanced \(k\)-median ⋮ A 2-approximation NC algorithm for connected vertex cover and tree cover ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Graph Connectivity in Log Steps Using Label Propagation ⋮ Deterministic Massively Parallel Connectivity ⋮ Time-optimal construction of overlay networks ⋮ Unnamed Item ⋮ Approximation algorithms for the priority facility location problem with penalties ⋮ An approximation algorithm for the \(k\)-median warehouse-retailer network design problem ⋮ The saga of minimum spanning trees ⋮ Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality ⋮ Integrated Supply Chain Management via Randomized Rounding ⋮ Graph summarization with quality guarantees ⋮ A fast minimum spanning tree algorithm based on \(K\)-means ⋮ The bridge-connectivity augmentation problem with a partition constraint ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Approximating node-weighted \(k\)-MST on planar graphs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Computing and minimizing the relative regret in combinatorial optimization with interval data ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ An approximation algorithm for the spherical \(k\)-means problem with outliers by local search ⋮ On the Strongly Connected and Biconnected Components of the Complement of Graphs

This page was built for publication: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation