|
DRUM >
College of Computer, Mathematical & Physical Sciences >
Computer Science >
Technical Reports from UMIACS >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1903/1272
|
| Title: | An Improved Approximation Algorithm For Vertex Cover with Hard Capacities |
| Authors: | Gandhi, Rajiv
Halperin, Eran
Khuller, Samir
Kortsarz, Guy
Srinivasan, Aravind |
| Type: | Technical Report |
| Issue Date: | 4-Apr-2003 |
| Series/Report no.: | UM Computer Science Department; CS-TR-4460
UMIACS; UMIACS-TR-2003-30 |
| 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 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
(\textit{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$-a... |
| URI: | http://hdl.handle.net/1903/1272 |
| Appears in Collections: | Technical Reports of the Computer Science Department
Technical Reports from UMIACS
|
Files in This Item:
| File |
Description |
Size | Format | No. of Downloads |
|---|
| CS-TR-4460.ps | | 241Kb | Postscript | 26 | View/Open |
|
Show full item record
All items in DRUM are protected by copyright, with all rights reserved.
|
