Polylogarithmic inapproximability
Authors:
Open Access
- 9 June 2003
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 585-594
Abstract
We provide the first hardness result of a polylogarithmic approximation ratio for a natural NP-hard optimization problem. We show that for every fixed ε>0, the GROUP-STEINER-TREE problem admits no efficient log2-ε k approximation, where k denotes the number of groups (or, alternatively, the input size), unless NP has quasi polynomial Las-Vegas algorithms. This hardness result holds even for input graphs which are Hierarchically Well-Separated Trees, introduced by Bartal [FOCS, 1996]. For these trees (and also for general trees), our bound is nearly tight with the log-squared approximation currently known. Our results imply that for every fixed ε>0, the DIRECTED-STEINER TREE problem admits no log2-ε n--approximation, where n is the number of vertices in the graph, under the same complexity assumption.Keywords
This publication has 15 references indexed in Scilit:
- Approximating theDomatic NumberSIAM Journal on Computing, 2002
- The Approximability of Constraint Satisfaction ProblemsSIAM Journal on Computing, 2001
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree ProblemJournal of Algorithms, 2000
- Divide-and-conquer approximation algorithms via spreading metricsJournal of the ACM, 2000
- Approximation Algorithms for Directed Steiner ProblemsJournal of Algorithms, 1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- A Parallel Repetition TheoremSIAM Journal on Computing, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Packing directed circuits fractionallyCombinatorica, 1995
- On the hardness of approximating minimization problemsJournal of the ACM, 1994