Dynamic programming based algorithms for set multicover and multiset multicover problems

DOI10.1016/j.tcs.2010.02.016zbMath1203.68316MaRDI QIDQ974740

Yuexuan Wang, Dongxiao Yu, Francis C. M. Lau, Qiang-Sheng Hua

Publication date: 7 June 2010

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

Full work available at URL: http://hdl.handle.net/10722/65464

zbMATH Keywords

algorithm; dynamic programming; set multicover; inclusion-exclusion; multiset multicover

Mathematics Subject Classification ID

90C39: Dynamic programming

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Set multi-covering via inclusion-exclusion
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• A fast approximation algorithm for the multicovering problem
• Approximating covering integer programs with multiplicity constraints
• Scheduling orders for multiple product types with due date related objectives
• Approximation algorithms for covering/packing integer programs
• An improved approximation algorithm for vertex cover with hard capacities
• Covering Problems with Hard Capacities
• Fourier meets M\"{o}bius: fast subset convolution
• Set Partitioning via Inclusion-Exclusion
• Exact Algorithms for Set Multicover and Multiset Multicover Problems
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Sum Multicoloring of Graphs
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Structural Information and Communication Complexity
• Approximation and Online Algorithms