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

DOI10.1145/1007352.1007363zbMath1192.68314OpenAlexW2139298384MaRDI QIDQ3580956

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

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

Asymmetric \(k\)-center with minimum coverage ⋮ Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs ⋮ Complete partitions of graphs ⋮ Asymmetry in \(k\)-center variants ⋮ Efficiently computing succinct trade-off curves

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