Asymmetric k -center is log * n -hard to approximate

DOI10.1145/1082036.1082038zbMath1323.68297OpenAlexW1966395945MaRDI QIDQ3546291

Julia Chuzhoy, Joseph (Seffi) Naor, Eran Halperin, Sudipto Guha, Sanjeev Khanna, Robert Krauthgamer, Guy Kortsarz

Publication date: 21 December 2008

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

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

zbMATH Keywords

approximation algorithmshardness of approximationasymmetric \(k\)-centermetric \(k\)-center

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (12)

A simple greedy approximation algorithm for the minimum connected \(k\)-center problem ⋮ Matroid and knapsack center problems ⋮ Client assignment problems for latency minimization ⋮ The connected \(p\)-center problem on block graphs with forbidden vertices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximability of Packing Disjoint Cycles ⋮ Approximability of packing disjoint cycles ⋮ Discrete sensor placement problems in distribution networks ⋮ Approximating Distance Measures for the Skyline ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ The weighted \(k\)-center problem in trees for fixed \(k\)

This page was built for publication: Asymmetric k -center is log ^* n -hard to approximate