Publication Details
Title: Approximating Dense Cases of Covering Problems
Author: M. Karpinski and A. Zelikovsky
Group: ICSI Technical Reports
Date: December 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-059.pdf
Overview:
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 Information:
ICSI Technical Report TR-96-059
Bibliographic Reference:
M. Karpinski and A. Zelikovsky. Approximating Dense Cases of Covering Problems. ICSI Technical Report TR-96-059, December 1996
Author: M. Karpinski and A. Zelikovsky
Group: ICSI Technical Reports
Date: December 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-059.pdf
Overview:
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 Information:
ICSI Technical Report TR-96-059
Bibliographic Reference:
M. Karpinski and A. Zelikovsky. Approximating Dense Cases of Covering Problems. ICSI Technical Report TR-96-059, December 1996