|
|||||
|
|
Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs |
|
| Affiliation: | 1. Dept. of Computer Science, University of Bonn, Germany;2. Hausdorff Center for Mathematics, University of Bonn, Germany |
| Abstract: |  We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-uniform k-partite hypergraphs. |
| Keywords: | Approximation algorithms Approximation hardness Vertex cover Set cover Dense hypergraphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |