Partial interval multicover: approximation and complexity

DOI10.1016/J.TCS.2026.115958MaRDI QIDQ7240328zbMATH OpenFDO

Authors Peng Li, Xiangzhi Tu, Zhao Zhang, Yixin Cao

Publication date 11 May 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115958

zbMATH Keywords

dynamic programmingmulticoverNP-completenesspartial coverpolynomial-time approximation scheme

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A 1/2-approximation algorithm for maximum interval multi-cover
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Approximation algorithm for the minimum interval partial multi-cover problem
• Complexity issues in vertex-colored graph pattern matching
• scientific article; zbMATH DE number 3121715 (Why is no real title available?)
• Improved performance of the greedy algorithm for partial cover
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• PTAS for densest \(k\)-subgraph in interval graphs

This page was built for publication: Partial interval multicover: approximation and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7240328)