## Abstract

In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph G = (V, E), the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. Previously, 2-approximation algorithms were developed with the assumption that multiple copies of a vertex may be chosen in the cover. If we are allowed to pick at most a given number of copies of each vertex, then the problem is significantly harder to solve. Chuzhoy and Naor (Proc. IEEE Symposium on Foundations of Computer Science, 481-489, 2002) have recently shown that the weighted version of this problem is at least as hard as set cover; they have also developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy-Naor bound of 3 and matching (up to lower-order terms) the best approximation ratio known for the vertex cover problem.

Original language | English (US) |
---|---|

Pages (from-to) | 164-175 |

Number of pages | 12 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 2719 |

State | Published - Dec 1 2003 |

## Keywords

- Approximation algorithms
- Capacitated covering
- Linear programming
- Randomized rounding
- Set cover
- Vertex cover

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science