File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783642106316_6
 Scopus: eid_2s2.075649086175
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Exact algorithms for set multicover and multiset multicover problems
Title  Exact algorithms for set multicover and multiset multicover problems 

Authors  
Issue Date  2009 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5878 LNCS, p. 3444 How to Cite? 
Abstract  Given a universe N containing n elements and a collection of multisets or sets over N, the multiset multicover (MSMC) 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 picked. First, we can exactly solve the MSMC without multiplicity constraints problem in O(((b+1)(c+1)) n ) time where b and c (c≤b and b≥2) respectively are the maximum coverage requirement and the maximum number of times that each element can appear in a multiset. To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, we can solve the SMC without multiplicity constraints problem in O((b+2) n ) time. Compared with the two recent results in [Hua et al., Set Multicovering via inclusionexclusion, Theoretical Computer Science, 410(3840):38823892 (2009)] and [Nederlof, J.: Inclusion Exclusion for hard problems. Master Thesis. Utrecht University, The Netherlands (2008)], we have given the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, 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 F) space where F denotes the total number of given multisets or sets over N. © 2009 SpringerVerlag Berlin Heidelberg. 
Persistent Identifier  http://hdl.handle.net/10722/151964 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Hua, QS  en_US 
dc.contributor.author  Yu, D  en_US 
dc.contributor.author  Lau, FCM  en_US 
dc.contributor.author  Wang, Y  en_US 
dc.date.accessioned  20120626T06:31:36Z   
dc.date.available  20120626T06:31:36Z   
dc.date.issued  2009  en_US 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5878 LNCS, p. 3444  en_US 
dc.identifier.issn  03029743  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/151964   
dc.description.abstract  Given a universe N containing n elements and a collection of multisets or sets over N, the multiset multicover (MSMC) 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 picked. First, we can exactly solve the MSMC without multiplicity constraints problem in O(((b+1)(c+1)) n ) time where b and c (c≤b and b≥2) respectively are the maximum coverage requirement and the maximum number of times that each element can appear in a multiset. To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, we can solve the SMC without multiplicity constraints problem in O((b+2) n ) time. Compared with the two recent results in [Hua et al., Set Multicovering via inclusionexclusion, Theoretical Computer Science, 410(3840):38823892 (2009)] and [Nederlof, J.: Inclusion Exclusion for hard problems. Master Thesis. Utrecht University, The Netherlands (2008)], we have given the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, 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 F) space where F denotes the total number of given multisets or sets over N. © 2009 SpringerVerlag Berlin Heidelberg.  en_US 
dc.language  eng  en_US 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_US 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_US 
dc.title  Exact algorithms for set multicover and multiset multicover problems  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Lau, FCM:fcmlau@cs.hku.hk  en_US 
dc.identifier.authority  Lau, FCM=rp00221  en_US 
dc.description.nature  link_to_subscribed_fulltext  en_US 
dc.identifier.doi  10.1007/9783642106316_6  en_US 
dc.identifier.scopus  eid_2s2.075649086175  en_US 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.075649086175&selection=ref&src=s&origin=recordpage  en_US 
dc.identifier.volume  5878 LNCS  en_US 
dc.identifier.spage  34  en_US 
dc.identifier.epage  44  en_US 
dc.publisher.place  Germany  en_US 
dc.identifier.scopusauthorid  Hua, QS=15060090400  en_US 
dc.identifier.scopusauthorid  Yu, D=30767911100  en_US 
dc.identifier.scopusauthorid  Lau, FCM=7102749723  en_US 
dc.identifier.scopusauthorid  Wang, Y=35222735000  en_US 