Dynamic programming based algorithms for set multicover and multiset multicover problems
type: Item
instance of: scholarly article
title: Dynamic programming based algorithms for set multicover and multiset multicover problems
zbMATH Open document ID: 1203.68316
author: Qiang-Sheng Hua
author: Yuexuan Wang
author: Dongxiao Yu
author: Francis C. M. Lau
published in: Theoretical Computer Science
publication date: 2010-06-07T00:00:00Z
full work available at URL: http://hdl.handle.net/10722/65464
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 5717730
zbMATH Keywords: set multicover
zbMATH Keywords: multiset multicover
zbMATH Keywords: inclusion-exclusion
zbMATH Keywords: dynamic programming
zbMATH Keywords: algorithm
MaRDI profile type: Publication
OpenAlex ID: W1994289544
cites work: Q4252268
cites work: Structural Information and Communication Complexity
cites work: Sum Multicoloring of Graphs
cites work: Set Partitioning via Inclusion-Exclusion
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: Covering Problems with Hard Capacities
cites work: An improved approximation algorithm for vertex cover with hard capacities
cites work: A fast approximation algorithm for the multicovering problem
cites work: Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
cites work: Q3002852
cites work: Exact Algorithms for Set Multicover and Multiset Multicover Problems
cites work: Set multi-covering via inclusion-exclusion
cites work: Approximation algorithms for covering/packing integer programs
cites work: Approximating covering integer programs with multiplicity constraints
cites work: Scheduling orders for multiple product types with due date related objectives
cites work: Fast Approximation Algorithms for Fractional Packing and Covering Problems
cites work: Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
cites work: New approaches to covering and packing problems
cites work: Improved Approximation Guarantees for Packing and Covering Integer Programs
cites work: Approximation and Online Algorithms
cites work: Q4258215
DOI: 10.1016/J.TCS.2010.02.016
Recommended article: Exact Algorithms for Set Multicover and Multiset Multicover Problems
Recommended article: Algorithms for the set covering problem
Recommended article: Problems and algorithms for covering arrays via set covers
Recommended article: Dynamic set cover: improved algorithms and lower bounds
Recommended article: Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
Recommended article: Dynamic programming in the problem of optimization of a covering
Recommended article: Approximation algorithm for the partial set multi-cover problem
Recommended article: Q3342591
Recommended article: A heuristic algorithm for the multi-criteria set-covering problems
Recommended article: Approximation and Online Algorithms
description: scientific article; zbMATH DE number 5717730