Exact algorithms for set multicover and multiset multicover problems

DOI10.1007/978-3-642-10631-6_6MaRDI QIDQ3652189zbMATH OpenOpenAlexFDO

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

Publication date 17 December 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10631-6_6

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Dynamic programming based algorithms for set multicover and multiset multicover problems
• Set multi-covering via inclusion-exclusion
• A fast approximation algorithm for the multicovering problem
• Approximation and Online Algorithms
• Approximation algorithm for partial set multicover versus full set multicover

Cited in

(20)

• A fast approximation algorithm for the multicovering problem
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Robust multicovers with budgeted uncertainty
• Exact multi-covering problems with geometric sets
• A novel decomposition approach to set covering problems by exploiting special structures
• On resilient feature selection: computational foundations of \(r\)-\(\mathbb{C} \)-reducts
• Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
• The robust minimal controllability problem
• An exact algorithm for the maximal covering problem
• Tight approximation bounds for maximum multi-coverage
• On nonlinear multi-covering problems
• The Exact Subset MultiCover problem
• Hardness and algorithms for electoral manipulation under media influence
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• The \textsc{Exact Subset MultiCover} problem
• On constrained minimum weight edge covers with applications to emergency planning
• Set multi-covering via inclusion-exclusion
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• A variable neighborhood search algorithm for the multimode set covering problem
• Dynamic programming based algorithms for set multicover and multiset multicover problems

This page was built for publication: Exact algorithms for set multicover and multiset multicover problems

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