We study dense instances of several covering problems. An instance of the set cover problem with m sets is dense if there is 0 such that any element belongs to at least m sets. We show that the dense set cover problem can be approximated with the performance ratio clogn for any c0 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 n vertices. We also study the vertex cover problem in -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 21+. The {em superdense} cases of all these problems are shown to be solvable in polynomial time.
展开▼
机译：我们研究了几个覆盖问题的密集实例。如果为0，则m个集合的集合覆盖问题的实例是密集的，这样任何元素都至少属于m个集合。我们表明，对于任何c0，密集集覆盖问题都可以用性能比clogn近似，并且不太可能是NP-hard。我们为n个顶点图中的密集Steiner树问题构造了多项式时间逼近方案，即对于每个端子至少邻近n个顶点的情况。我们还研究了-密集图中的顶点覆盖问题。尽管如一般图中所示，此问题仍然难以解决MAX-SNP问题，但我们发现性能比为21+的更好近似算法。所有这些问题的{ em superdense}情况在多项式时间内显示为可解决的。
展开▼
