An Improved Approximation Algorithm For Vertex Cover with Hard Capacities

Simple item page
dc.contributor.authorGandhi, Rajiven_US
dc.contributor.authorHalperin, Eranen_US
dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorKortsarz, Guyen_US
dc.contributor.authorSrinivasan, Aravinden_US
dc.date.accessioned2004-05-31T23:27:10Z
dc.date.available2004-05-31T23:27:10Z
dc.date.created2003-03en_US
dc.date.issued2003-04-04en_US
dc.description.abstractIn 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$-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. UMIACS-TR-2003-30en_US
dc.format.extent247161 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/1272
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4460en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2003-30en_US
dc.titleAn Improved Approximation Algorithm For Vertex Cover with Hard Capacitiesen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
CS-TR-4460.ps
Size:
241.37 KB
Format:
Postscript Files
Download

Collections

Technical Reports from UMIACS
Technical Reports of the Computer Science Department