Asymmetric k -center is log * n -hard to approximate
DOI10.1145/1082036.1082038zbMATH Open1323.68297OpenAlexW1966395945MaRDI QIDQ3546291FDOQ3546291
Authors: Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Robert Krauthgamer, Joseph (Seffi) Naor, 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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cited In (18)
- AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
- Approximability of Packing Disjoint Cycles
- Approximating Distance Measures for the Skyline
- Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
- Title not available (Why is that?)
- Approximability of packing disjoint cycles
- A simple greedy approximation algorithm for the minimum connected \(k\)-center problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Asymmetry in \(k\)-center variants
- The connected \(p\)-center problem on block graphs with forbidden vertices
- Asymmetric \(k\)-center with minimum coverage
- On perturbation resilience of non-uniform \(k\)-center
- The weighted \(k\)-center problem in trees for fixed \(k\)
- Discrete sensor placement problems in distribution networks
- Asymmetry in \(k\)-center variants
- Client assignment problems for latency minimization
This page was built for publication: Asymmetric k -center is log * n -hard to approximate
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546291)
