Metraipolis › archive › dc_fd802eff0b7b

Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension — arXiv:2608.03801

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.03801
License (as archived): CC0-1.0
Archived: 2026-10-31T13:09:33.562Z
SHA-256 of the archived text: 139186a773bef43adbd817ac9e8cce5b6f5b408228d574b91a9356f3b482baad
Stable URL of this page: https://metraipolis.com/documento/dc_fd802eff0b7b

How to cite

Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension — arXiv:2608.03801 — arXiv (en), https://arxiv.org/abs/2608.03801 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fd802eff0b7b (Metraipolis archive dc_fd802eff0b7b, sha256 139186a773bef43adbd817ac9e8cce5b6f5b408228d574b91a9356f3b482baad)

BibTeX

@misc{dcfd802eff0b7b,
  title = {Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension — arXiv:2608.03801},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.03801},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fd802eff0b7b; sha256 139186a773bef43adbd817ac9e8cce5b6f5b408228d574b91a9356f3b482baad},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.03801. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Maximum Coverage and Partial Set Cover are fundamental parameterized covering problems. The former fixes a budget $k$ and maximizes coverage; the latter meets a target with as few sets as possible. Badanidiyuru, Kleinberg, and Lee (SoCG 2012) give an EPAS for the former on bounded-VC set systems, while Jain et al. (SODA 2023) show that on $K_{d,d}$-free incidence graphs, $k+1$ sets suffice whenever $k$ sets meet the target. We ask whether this guarantee extends to all bounded-VC set systems. Our first result is negative. Unless FPT = W[1], Partial Set Cover admits no parameterized $(2-\delta)$-approximation even at VC-dimension seven. Under ETH, it has no parameterized approximation scheme there and no $2^{o(d)}$-approximation at VC-dimension $d$. On the positive side, bounded semi-ladder index restores this guarantee. It is stronger than bounded VC-dimension but strictly generalizes the $K_{d,d}$-free setting. For Weighted Partial Set Cover, if $k$ sets cover weight $W$, we find $k+1$ sets covering weight $W$ in $2^{O(\Gamma k\log k)}N$ time, where $\Gamma$ is the downward intersection complexity and $N$ is the input size. The framework supports per-class targets and matroid independence, with applications to partial dominating set and geometric and bounded-size covering. Finally, we give a deterministic FPT reduction from Weighted CC-MaxSAT to a bounded family of Weighted Maximum Coverage instances, preserving incidence structure and approximation schemes with constant-factor accuracy loss. This gives an EPAS at bounded semi-ladder index. We improve the deterministic BKL bounded-VC implementation; combined with our reduction, it yields a $2^{\widetilde{O}(kd/\varepsilon)}N^{O(1)}$-time EPAS for bounded-VC Weighted CC-MaxSAT.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-05 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.03801 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T12:57:43.020Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).