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<d<1. What is the best possible running time
for achieving such approximation? This question was answered implicitly in the
work of Moshkovitz [Theory of Computing, 2015]: Assuming both the Projection
Games Conjecture (PGC) and the Exponential-Time Hypothesis (ETH), any ((1-d) ln
n)-approximation algorithm for Set-Cover must run in time >= 2^{n^{c d}}, for
some constant 0<d<1.
We study the questions along this line. First, we show that under ETH and PGC
any ((1-d) \ln 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).
We 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 < d < 1. We show the lower bound of GST: any
(log^{2-d}n)-approximation for GST must run in time >=
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.
