Approximation algorithm for the maximum interval multi-cover problem

DOI10.1007/978-981-97-7798-3_3MaRDI QIDQ7405611zbMATH OpenFDO

Authors Yuxuan Xu, Yingli Ran, Zhao Zhang

Publication date 2024

Full work available at URL https://doi.org/10.1007/978-981-97-7798-3_3

zbMATH Keywords

approximation ratiodynamic programmingmaximum covermulti-cover

Mathematics Subject Classification ID

Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial optimization (90C27) Dynamic programming (90C39)

Cites work

• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• scientific article; zbMATH DE number 7788517 (Why is no real title available?)
• New variations of the maximum coverage facility location problem
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• PTAS for densest \(k\)-subgraph in interval graphs
• The budgeted maximum coverage problem
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

This page was built for publication: Approximation algorithm for the maximum interval multi-cover problem

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