Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/118385
| Title: | Partial interval multicover : approximation and complexity | Authors: | Tu, X Zhang, Z Cao, Y Li, P |
Issue Date: | 15-Jun-2026 | Source: | Theoretical computer science, 15 June 2026, v. 1075, 115958 | Abstract: | We study a variant of set cover on the real line, where elements are points, sets are intervals, and each point has an integer demand; a point is fully covered when it is contained in at least its demand many chosen intervals. The objective is to select the fewest intervals that fully cover at least a specified number of points. We present the first polynomial-time approximation scheme (PTAS) for the unweighted version of this problem and show that a natural weighted generalization is NP-complete. | Keywords: | Theoretical computer science Multicover NP-completeness Partial cover Polynomial-time approximation scheme |
Publisher: | Elsevier BV | Journal: | Theoretical computer science | ISSN: | 0304-3975 | DOI: | 10.1016/j.tcs.2026.115958 | Rights: | © 2026 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ ). The following publication Li, P., Tu, X., Zhang, Z., & Cao, Y. (2026). Partial interval multicover: Approximation and complexity. Theoretical Computer Science, 1075, 115958 is available at https://doi.org/10.1016/j.tcs.2026.115958. |
| Appears in Collections: | Journal/Magazine Article |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 1-s2.0-S0304397526002173-main.pdf | 2.03 MB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.