Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-004 | 19th February 1997 00:00

Approximating Dense Cases of Covering Problems



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.


Comment #1 to TR97-004 | 30th April 1998 15:05

Evaluation of an Approximate Algorithm for the Everywhere Dense Vertex Cover Problem Comment on: TR97-004

Comment #1
Authors: Anton Eremeev
Accepted on: 30th April 1998 15:05
Downloads: 2212


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}$.

ISSN 1433-8092 | Imprint