@online{Cygan_arXiv1811.00710,
TITLE = {{On Subexponential Running Times for Approximating Directed Steiner Tree and Related Problems}},
AUTHOR = {Cygan, Marek and Kortsarz, Guy and Laekhanukit, Bundit},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1811.00710},
EPRINT = {1811.00710},
EPRINTTYPE = {arXiv},
YEAR = {2018},
MARGINALMARK = {$\bullet$},
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 0= exp((1+o(1)){log^{d-c}n}), for any c>0, 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.},
}