Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

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.

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/429

[2] https://www.cs.princeton.edu/research/techreps/author/255

[3] ftp://ftp.cs.princeton.edu/techreports/1997/542.ps.gz