File Download
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1016/j.tcs.2010.02.016
 Scopus: eid_2s2.077953288529
 WOS: WOS:000278564600005
 Find via
Supplementary

Bookmarks:
 CiteULike: 1
 Citations:
 Appears in Collections:
Article: Dynamic programming based algorithms for set multicover and multiset multicover problems
Title  Dynamic programming based algorithms for set multicover and multiset multicover problems  

Authors  
Keywords  Algorithm Dynamic programming Inclusionexclusion Multiset multicover Set multicover  
Issue Date  2010  
Publisher  Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs  
Citation  Theoretical Computer Science, 2010, v. 411 n. 2628, p. 24672474 How to Cite?  
Abstract  Given a universe N containing n elements and a collection of multisets or sets over N, the multiset multicover (MSMC) problem or the set multicover (SMC) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of multisets or sets. In this paper, we give various exact algorithms for these two problems with or without constraints on the number of times a multiset or set may be chosen. First, we show that the MSMC without multiplicity constraints problem can be solved in O* ((b + 1)n  F ) time and polynomial space, where b is the maximum coverage requirement and  F  denotes the total number of given multisets over N. (The O* notation suppresses a factor polynomial in n.) To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, by combining dynamic programming and the inclusionexclusion principle, we can exactly solve the SMC without multiplicity constraints problem in O ((b + 2)n) time. Compared with two recent results, in [Q.S. Hua, Y. Wang, D. Yu, F.C.M. Lau, Set multicovering via inclusionexclusion, Theoretical Computer Science, 410 (3840) (2009) 38823892] and [J. Nederlof, Inclusion exclusion for hard problems, Master Thesis, Utrecht University, The Netherlands, 2008], respectively, ours is the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, by directly using dynamic programming, we give the first known exact algorithm for the MSMC or the SMC with multiplicity constraints problem in O ((b + 1)n  F ) time and O* ((b + 1)n) space. This algorithm can also be easily adapted as a constructive algorithm for the MSMC without multiplicity constraints problem. © 2010 Elsevier B.V. All rights reserved.  
Persistent Identifier  http://hdl.handle.net/10722/65464  
ISSN  2019 Impact Factor: 0.747 2015 SCImago Journal Rankings: 0.720  
ISI Accession Number ID 
Funding Information: The first author would like to thank Simai He for helpful discussions. We also thank the anonymous reviewers (of the preliminary version) for their insightful comments. This research is supported in part by Hong Kong RGCGRF grants (7136/07E and 714009E), and the National Basic Research Program of China Grant 2007CB807900, 2007CB807901.  
References 
DC Field  Value  Language 

dc.contributor.author  Hua, QS  en_HK 
dc.contributor.author  Wang, Y  en_HK 
dc.contributor.author  Yu, D  en_HK 
dc.contributor.author  Lau, FCM  en_HK 
dc.date.accessioned  20100809T08:35:40Z   
dc.date.available  20100809T08:35:40Z   
dc.date.issued  2010  en_HK 
dc.identifier.citation  Theoretical Computer Science, 2010, v. 411 n. 2628, p. 24672474  en_HK 
dc.identifier.issn  03043975  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/65464   
dc.description.abstract  Given a universe N containing n elements and a collection of multisets or sets over N, the multiset multicover (MSMC) problem or the set multicover (SMC) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of multisets or sets. In this paper, we give various exact algorithms for these two problems with or without constraints on the number of times a multiset or set may be chosen. First, we show that the MSMC without multiplicity constraints problem can be solved in O* ((b + 1)n  F ) time and polynomial space, where b is the maximum coverage requirement and  F  denotes the total number of given multisets over N. (The O* notation suppresses a factor polynomial in n.) To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, by combining dynamic programming and the inclusionexclusion principle, we can exactly solve the SMC without multiplicity constraints problem in O ((b + 2)n) time. Compared with two recent results, in [Q.S. Hua, Y. Wang, D. Yu, F.C.M. Lau, Set multicovering via inclusionexclusion, Theoretical Computer Science, 410 (3840) (2009) 38823892] and [J. Nederlof, Inclusion exclusion for hard problems, Master Thesis, Utrecht University, The Netherlands, 2008], respectively, ours is the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, by directly using dynamic programming, we give the first known exact algorithm for the MSMC or the SMC with multiplicity constraints problem in O ((b + 1)n  F ) time and O* ((b + 1)n) space. This algorithm can also be easily adapted as a constructive algorithm for the MSMC without multiplicity constraints problem. © 2010 Elsevier B.V. All rights reserved.  en_HK 
dc.language  eng   
dc.publisher  Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs  en_HK 
dc.relation.ispartof  Theoretical Computer Science  en_HK 
dc.rights  Theoretical Computer Science. Copyright © Elsevier BV.   
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.subject  Algorithm  en_HK 
dc.subject  Dynamic programming  en_HK 
dc.subject  Inclusionexclusion  en_HK 
dc.subject  Multiset multicover  en_HK 
dc.subject  Set multicover  en_HK 
dc.title  Dynamic programming based algorithms for set multicover and multiset multicover problems  en_HK 
dc.type  Article  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=03043975&volume=411&issue=2628&spage=2467&epage=2474&date=2010&atitle=Dynamic+programming+based+algorithms+for+set+multicover+and+multiset+multicover+problems   
dc.identifier.email  Lau, FCM:fcmlau@cs.hku.hk  en_HK 
dc.identifier.authority  Lau, FCM=rp00221  en_HK 
dc.description.nature  postprint   
dc.identifier.doi  10.1016/j.tcs.2010.02.016  en_HK 
dc.identifier.scopus  eid_2s2.077953288529  en_HK 
dc.identifier.hkuros  172270   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.077953288529&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  411  en_HK 
dc.identifier.issue  2628  en_HK 
dc.identifier.spage  2467  en_HK 
dc.identifier.epage  2474  en_HK 
dc.identifier.isi  WOS:000278564600005   
dc.publisher.place  Netherlands  en_HK 
dc.identifier.scopusauthorid  Hua, QS=15060090400  en_HK 
dc.identifier.scopusauthorid  Wang, Y=35222735000  en_HK 
dc.identifier.scopusauthorid  Yu, D=30767911100  en_HK 
dc.identifier.scopusauthorid  Lau, FCM=7102749723  en_HK 
dc.identifier.citeulike  6867040   