betaFeedback

WorksComputer Science

Partial Interval Multicover Is NP-Complete Even for Unit Intervals

Abstract

For a interval family \calI, a point set X⊆RX\subseteq\mathbb R, demands d:X→Z≥0d:X\to\Z_{\ge0}, and p∈Z≥0p\in\Z_{\ge0}, partial interval multicover asks for a subfamily S\subseteq\calI minimizing ∣S∣|S| subject to |\{x\in X:\dep_S(x)\ge d(x)\}|\ge p, \qquad \dep_S(x)=|\{I\in S:x\in I\}|. We prove that the unweighted decision problem is NP-complete even for unit intervals, answering the open question in~\cite{Li2026}.

Paper details

vlnc:W_jnga29pg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…