×

Approximating dense cases of covering problems. (English) Zbl 0896.68078

Pardalos, Panos M. (ed.) et al., Network design: connectivity and facilities location. DIMACS workshop, April 28–30, 1997. Providence, RI: AMS, American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 40, 169-178 (1998).
Summary: We study dense instances of several covering problems. An instance of the set cover problem with \(m\) sets is dense if there is \(\varepsilon> 0\) such that any element of the ground set \(X\) belongs to at least \(\varepsilon\cdot m\) sets. We show that the dense set cover problem can be approximated with the performance ratio \(c\cdot\log| X|\) for any \(c>0\) though it is unlikely to be NP-hard. A polynomial-time approximation scheme is constructed for the dense Steiner tree problem in \(n\)-vertex graphs, i.e. for the case when each terminal is adjacent to at least \(\varepsilon\cdot n\) vertices. We also study the vertex cover problem in dense graphs, i.e. graphs with the bounded minimum or average vertex degree. A better approximation algorithm is suggested. Its performance ratio is \({2\over 1+\varepsilon}\) and \({2\over 2- \sqrt{1- \varepsilon}}\) for graphs with \(\varepsilon| V|\)-bounded minimum and average vertex degree, respectively. We also consider superdense (complementary to sparse) cases of all these problems.
For the entire collection see [Zbl 0889.00029].

MSC:

68Q25 Analysis of algorithms and problem complexity
90C27 Combinatorial optimization
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite