Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/118385
PIRA download icon_1.1View/Download Full Text
DC FieldValueLanguage
dc.contributorDepartment of Computingen_US
dc.creatorTu, Xen_US
dc.creatorZhang, Zen_US
dc.creatorCao, Yen_US
dc.creatorLi, Pen_US
dc.date.accessioned2026-04-13T08:25:43Z-
dc.date.available2026-04-13T08:25:43Z-
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10397/118385-
dc.language.isoenen_US
dc.publisherElsevier BVen_US
dc.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/ ).en_US
dc.rightsThe 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.en_US
dc.subjectTheoretical computer scienceen_US
dc.subjectMulticoveren_US
dc.subjectNP-completenessen_US
dc.subjectPartial coveren_US
dc.subjectPolynomial-time approximation schemeen_US
dc.titlePartial interval multicover : approximation and complexityen_US
dc.typeJournal/Magazine Articleen_US
dc.identifier.volume1075en_US
dc.identifier.doi10.1016/j.tcs.2026.115958en_US
dcterms.abstractWe 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.en_US
dcterms.accessRightsopen accessen_US
dcterms.bibliographicCitationTheoretical computer science, 15 June 2026, v. 1075, 115958en_US
dcterms.isPartOfTheoretical computer scienceen_US
dcterms.issued2026-06-15-
dc.identifier.artn115958en_US
dc.description.validate202604 bcchen_US
dc.description.oaVersion of Recorden_US
dc.identifier.FolderNumbera4368, OA_TA-
dc.identifier.SubFormID52645-
dc.description.fundingSourceOthersen_US
dc.description.fundingTextSupported in part by the National Natural Science Foundation of China (NSFC) under grant 12571342. Supported in part by the National Natural Science Foundation of China (NSFC) under grant 62372394. Supported in part by Chongqing Natural Science Foundation Innovation and Development Joint Fund (Municipal Education Commission) under grant CSTB2022NSCQ-LZX0003en_US
dc.description.pubStatusPublisheden_US
dc.description.TAElsevier (2026)en_US
dc.description.oaCategoryTAen_US
Appears in Collections:Journal/Magazine Article
Files in This Item:
File Description SizeFormat 
1-s2.0-S0304397526002173-main.pdf2.03 MBAdobe PDFView/Open
Open Access Information
Status open access
File Version Version of Record
Access
View full-text via PolyU eLinks SFX Query
Show simple item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.