Paper Info
Title
On subexponential running times for approximating directed Steiner tree and related problems.
Abstract
This paper concerns proving almost tight (super-polynomial) running times, for achieving desired approximation ratios for various problems. To illustrate, the question we study, let us consider the Set-Cover problem with n elements and m sets. Now we specify our goal to approximate Set-Cover to a factor of (1-d)ln n, for a given parameter 0 = 2^{n^{c d}}, for some constant 0u003cdu003c1. study the questions along this line. First, we show that under ETH and PGC any ((1-d) n)-approximation for Set-Cover requires 2^{n^{d}}-time. This (almost) matches the running time of 2^{O(n^d)} for approximating Set-Cover to a factor (1-d) ln n by Cygan et al. [IPL, 2009]. Our result is tight up to the constant multiplying the n^{d} terms in the exponent. This lower bound applies to all of its generalizations, e.g., Group Steiner Tree (GST), Directed Steiner (DST), Covering Steiner Tree (CST), Connected Polymatroid (CP). We also show that in almost exponential time, these problems reduce to Set-Cover: We show (1-d)ln n approximation algorithms for all these problems that run in time 2^{n^{d log n } poly(m). also study log^{2-d}n approximation for GST. Chekuri-Pal [FOCS, 2005] showed that GST admits (log^{2-d}n)-approximation in time exp(2^{log^{d+o(1)}n}), for any 0 = exp((1+o(1)){log^{d-c}n}), for any cu003e0, unless the ETH is false. Our result follows by analyzing the work of Halperin and Krauthgamer [STOC, 2003]. The same lower and upper bounds hold for CST.
Year
Venue
DocType
2018
arXiv: Data Structures and Algorithms
Journal
Volume
Citations 
PageRank 
abs/1811.00710
0
0.34
References 
Authors
19
3
Name
Order
Citations
PageRank
Marek Cygan155640.52
Guy Kortsarz21539126.16
Bundit Laekhanukit312916.93