Capacitated Partition Vertex Cover and Partition Edge Cover
Rajni Dabas, Samir Khuller, Emilie Rivkin · 2025
Read Capacitated Partition Vertex Cover and Partition Edge Cover by Rajni Dabas, Samir Khuller, Emilie Rivkin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-17844.txt.
Description
Rajni Dabas, Samir Khuller, and Emilie Rivkin study covering problems, where a small set of points must guard a large set of groups. In their main problem, each group of hyperedges needs a set share covered, and each chosen vertex has a cap on how much it can cover. The problem blends several classic covering tasks into one.
The authors give fast methods that come close to the best possible answer. One method handles the case where a vertex may be reused, and another handles the stricter single use case. They also solve a weighted edge cover variant exactly, with a cleaner and faster method than earlier work on the unweighted version.
Catalog record
| CREATOR | Rajni Dabas, Samir Khuller, Emilie Rivkin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-17844