Approximating dense cases of covering problems
Marek Karpiński, Alex Zelikovsky · DIMACS series in discrete mathematics and theoretical computer science · 1998
We study dense cases of several covering problems. An instance of the set cover problem with m sets is dense if there is ffl ? 0 such that any element belongs to at least fflm 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 ffln vertices. We also study the vertex cover problem in ffl-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+ffl . The superdense cases of all these problems are shown to be solvable in polynomial time. Dept. of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley. Research partially done while visiting Dept. of Computer Science, P...