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

CREATORRajni Dabas, Samir Khuller, Emilie Rivkin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-17844

Browse the full library · About the Tower of Babel