
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 1996  Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V  
8935

Approximating Dense Cases of Covering Problems
Marek Karpinski, Alexander Zelikovsky [Download PostScript] [Download PDF] 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 $c\log n$ for any $c>0$ and it is unlikely to be NPhard. We construct a polynomialtime 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 MAXSNPhard as in general graphs, we find a better approximation algorithm with the performance ratio $2\over{1+\epsilon}$. The {\em superdense} cases of all these problems are shown to be solvable in polynomial time. 

Last Change:
11/05/14 at 10:01:20
English 
Universität Bonn > Institut für Informatik > Abteilung V 