Approximating Dense Cases of Covering Problems

TitleApproximating Dense Cases of Covering Problems
Publication TypeTechnical Report
Year of Publication1996
AuthorsKarpinski, M., & Zelikovsky A.
Other Numbers1067

We study dense cases of several covering problems. An instance of the set cover problem with m sets is dense if there is e > 0 such that any element belongs to at least em sets. We show that the dense set cover problem can be approximated with the performance ratio c log n for any c > 0 and it is unlikely to be NP-hard. We construct a polynomial-time approximation scheme for the dense Steiner tree problem in n-vertex graphs, i.e. for the case when each terminal is adjacent to at least n-vertices. We also study the vertex cover problem in e-dense graphs. Though this problem is shown to be still MAX-SNP-hard as in general graphs, we find a better approximation algorithm with the performance ratio 2/1+?. The superdense cases of all these problems are shown to be solvable in polynomial time.

Bibliographic Notes

ICSI Technical Report TR-96-059

Abbreviated Authors

M. Karpinski and A. Zelikovsky

ICSI Publication Type

Technical Report