Abstract | ||
---|---|---|
The worst-case fastest known algorithm for the Set Cover problem on universes with n elements still essentially is the simple O^*(2^n)-time dynamic programming algorithm, and no non-trivial consequences of an O^*(1.01^n)-time algorithm are known. Motivated by this chasm, we study the following natural question: Which instances of Set Cover can we solve faster than the simple dynamic programming algorithm? Specifically, we give a Monte Carlo algorithm that determines the existence of a set cover of size sigma*n in O^*(2^{(1-Omega(sigma^4))n}) time. Our approach is also applicable to Set Cover instances with exponentially many sets: By reducing the task of finding the chromatic number of a given n-vertex graph G to Set Cover in the natural way, we show there is an O^*(2^{(1-Omega(sigma^4))n})-time randomized algorithm that given integer s = sigma*n, outputs NO if u003e s and YES with constant probability if chi(G) u003c= s - 1.On a high level, our results are inspired by the representation method of Howgrave-Graham and Joux~[EUROCRYPTu002710] and obtained by only evaluating a randomly sampled subset of the table entries of a dynamic programming algorithm. |
Year | DOI | Venue |
---|---|---|
2016 | 10.4230/LIPIcs.ESA.2016.69 | european symposium on algorithms |
DocType | Volume | Citations |
Journal | abs/1608.03439 | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jesper Nederlof | 1 | 294 | 24.22 |