We study dense instances 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
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 2\over{1+\epsilon}. The {\em superdense} cases of all these
problems are shown to be solvable in polynomial time.
We generalize the DVC algorithm for the weighted case of vertex cover
problem (VCP) and study the performance of this algorithm. An extension
of result from TR97-004 for the weighted case is proposed in terms of a
new density parameter. Given a graph G(V,E) let there be \rho >0
such that w(O(v)) \geq \rho w(V) for any vertex v \in V. Here
w(O(v)) is the total weight of the neighbours of v, and w(V) is
the total weight of V. Then \frac{2}{1+\rho} performance guarantee
holds for an algorithm similar to DVC. The value \rho can be easily
estimated for everywhere \varepsilon-dense VCP, if there is such d
that w_u \leq dw_v for any pair of vertices u and v. The
generalization of DVC allows us to propose another polinomial-time
algorithm for the weighted VCP with the performance ratio as a function
on |V| which is less than \frac{2}{1+\rho}.
