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

DOI10.1145/1082036.1082038MaRDI QIDQ3546291zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmsasymmetric \(k\)-centerhardness of approximationmetric \(k\)-center

Mathematics Subject Classification ID

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

Recommendations

• Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
• scientific article; zbMATH DE number 1757943
• AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
• Asymmetric \(k\)-center with minimum coverage
• \(k\)-center clustering under perturbation resilience

Cited in

(19)

• On perturbation resilience of non-uniform k-center
• The weighted \(k\)-center problem in trees for fixed \(k\)
• Asymmetric \(k\)-center with minimum coverage
• Client assignment problems for latency minimization
• Discrete sensor placement problems in distribution networks
• Asymmetry in \(k\)-center variants
• A simple greedy approximation algorithm for the minimum connected k-center problem
• Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
• The connected p-center problem on block graphs with forbidden vertices
• AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
• scientific article; zbMATH DE number 1757943 (Why is no real title available?)
• scientific article; zbMATH DE number 871893 (Why is no real title available?)
• scientific article; zbMATH DE number 7378621 (Why is no real title available?)
• Approximating Distance Measures for the Skyline
• Approximability of packing disjoint cycles
• Approximability of Packing Disjoint Cycles
• Asymmetry in \(k\)-center variants
• scientific article; zbMATH DE number 7758333 (Why is no real title available?)
• On the hardness of approximation of the fair k-center problem

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)