ECCC-Report TR97-004https://eccc.weizmann.ac.il/report/1997/004Comments and Revisions published for TR97-004en-usThu, 30 Apr 1998 15:05:50 +0300
Comment 1
| Evaluation of an Approximate Algorithm for the Everywhere Dense Vertex Cover Problem Comment on: TR97-004 |
Anton Eremeev
https://eccc.weizmann.ac.il/report/1997/004#comment1 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}$.
Thu, 30 Apr 1998 15:05:50 +0300https://eccc.weizmann.ac.il/report/1997/004#comment1
Paper TR97-004
| Approximating Dense Cases of Covering Problems |
Marek Karpinski,
Alexander Zelikovsky
https://eccc.weizmann.ac.il/report/1997/004We 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.
Wed, 19 Feb 1997 13:17:58 +0200https://eccc.weizmann.ac.il/report/1997/004