File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Dynamic programming based algorithms for set multicover and multiset multicover problems

TitleDynamic programming based algorithms for set multicover and multiset multicover problems
Authors
KeywordsAlgorithm
Dynamic programming
Inclusion-exclusion
Multiset multicover
Set multicover
Issue Date2010
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2010, v. 411 n. 26-28, p. 2467-2474 How to Cite?
AbstractGiven 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 inclusion-exclusion 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 multi-covering via inclusion-exclusion, Theoretical Computer Science, 410 (38-40) (2009) 3882-3892] 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 Identifierhttp://hdl.handle.net/10722/65464
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
Funding AgencyGrant Number
Hong Kong RGC-GRF7136/07E
714009E
National Basic Research Program of China2007CB807900
2007CB807901
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 RGC-GRF grants (7136/07E and 714009E), and the National Basic Research Program of China Grant 2007CB807900, 2007CB807901.

References

 

DC FieldValueLanguage
dc.contributor.authorHua, QSen_HK
dc.contributor.authorWang, Yen_HK
dc.contributor.authorYu, Den_HK
dc.contributor.authorLau, FCMen_HK
dc.date.accessioned2010-08-09T08:35:40Z-
dc.date.available2010-08-09T08:35:40Z-
dc.date.issued2010en_HK
dc.identifier.citationTheoretical Computer Science, 2010, v. 411 n. 26-28, p. 2467-2474en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/65464-
dc.description.abstractGiven 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 inclusion-exclusion 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 multi-covering via inclusion-exclusion, Theoretical Computer Science, 410 (38-40) (2009) 3882-3892] 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.languageeng-
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.-
dc.subjectAlgorithmen_HK
dc.subjectDynamic programmingen_HK
dc.subjectInclusion-exclusionen_HK
dc.subjectMultiset multicoveren_HK
dc.subjectSet multicoveren_HK
dc.titleDynamic programming based algorithms for set multicover and multiset multicover problemsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=411&issue=26-28&spage=2467&epage=2474&date=2010&atitle=Dynamic+programming+based+algorithms+for+set+multicover+and+multiset+multicover+problems-
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1016/j.tcs.2010.02.016en_HK
dc.identifier.scopuseid_2-s2.0-77953288529en_HK
dc.identifier.hkuros172270-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77953288529&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume411en_HK
dc.identifier.issue26-28en_HK
dc.identifier.spage2467en_HK
dc.identifier.epage2474en_HK
dc.identifier.isiWOS:000278564600005-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridHua, QS=15060090400en_HK
dc.identifier.scopusauthoridWang, Y=35222735000en_HK
dc.identifier.scopusauthoridYu, D=30767911100en_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK
dc.identifier.citeulike6867040-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats