Quick k-Median, k-Center, and Facility Location for Sparse Graphs

DOI10.1137/S0097539701388884zbMath1099.68136MaRDI QIDQ4651542

Mikkel Thorup

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

location problemsshortest pathsfacility location\(k\)-center\(k\)-medianefficient approximation algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (12)

Map graphs having witnesses of large girth ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ The k-centre problem for classes of cyclic words ⋮ A distributed O(1)-approximation algorithm for the uniform facility location problem ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Sublinear-time Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Probabilistic smallest enclosing ball in high dimensions via subgradient sampling ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Decomposition of Map Graphs with Applications. ⋮ A sublinear-time approximation scheme for bin packing

This page was built for publication: Quick k-Median, k-Center, and Facility Location for Sparse Graphs