Approximating Dense Cases of Covering Problems
Report ID: TR-542-97Author: Zelikovsky, Alexander / Karpinski, Marek
Date: 1996-12-00
Pages: 9
Download Formats: |Postscript|
Abstract:
We study dense cases of several covering problems. An instance of the set cover problem with $m$ sets is dense if there is $epsilon>0$ such that any element belongs to at least $epsilon m$ sets. We show that the dense set cover problem can be approximated with the performance ratio $clog 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 $epsilon n$ vertices. We also study the vertex cover problem in $epsilon$-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 $2over{1+epsilon}$. The {em superdense} cases of all these problems are shown to be solvable in polynomial time.