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

DOI10.1145/1007352.1007363MaRDI QIDQ3580956zbMATH OpenOpenAlexFDO

Authors Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Joseph (Seffi) Naor, 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

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

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

(12)

• Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
• Asymmetric \(k\)-center with minimum coverage
• Asymmetry in \(k\)-center variants
• Efficiently computing succinct trade-off curves
• Asymmetric k -center is log ^* n -hard to approximate
• 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?)
• Asymmetry in \(k\)-center variants
• Constant-factor greedy algorithms for the asymmetric \(p\)-center problem in parameterized complete digraphs
• An improved two-stage approximation algorithm for the k-supplier problem with parameterized triangle inequality
• Complete partitions of graphs

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 Q3580956)