Loading...
Please wait, while we are loading the content...
Similar Documents
An improved approximation algorithm for vertex cover with hard capacities (extended abstract)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Gandhi, Rajiv Halperin, Eran Khuller, Samir Kortsarz, Guy Srinivasan, Aravind |
| Copyright Year | 2003 |
| 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, improv- ing the Chuzhoy-Naor bound of 3 and matching (up to lower-order terms) the best approximation ratio known for the vertex cover problem. |
| Starting Page | 164 |
| Ending Page | 175 |
| Page Count | 12 |
| File Format | PDF HTM / HTML |
| Volume Number | 2719 |
| Alternate Webpage(s) | http://www.cs.umd.edu/Library/TRs/CS-TR-4460/CS-TR-4460.ps |
| Alternate Webpage(s) | http://www.icsi.berkeley.edu/~heran/publications/papers/hardCap.ps |
| Alternate Webpage(s) | http://crab.rutgers.edu/~rajivg/publications/hardCap.ps |
| Alternate Webpage(s) | http://www.cs.umd.edu/users/samir/grant/icalp03.ps |
| Alternate Webpage(s) | http://crab.rutgers.edu/~rajivg/publications/hardCap.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
