File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Exact algorithms for set multicover and multiset multicover problems

TitleExact algorithms for set multicover and multiset multicover problems
Authors
Issue Date2009
PublisherSpringer 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. 34-44 How to Cite?
AbstractGiven 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 Multi-covering via inclusion-exclusion, Theoretical Computer Science, 410(38-40):3882-3892 (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 Springer-Verlag Berlin Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/151964
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorHua, QSen_US
dc.contributor.authorYu, Den_US
dc.contributor.authorLau, FCMen_US
dc.contributor.authorWang, Yen_US
dc.date.accessioned2012-06-26T06:31:36Z-
dc.date.available2012-06-26T06:31:36Z-
dc.date.issued2009en_US
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2009, v. 5878 LNCS, p. 34-44en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/151964-
dc.description.abstractGiven 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 Multi-covering via inclusion-exclusion, Theoretical Computer Science, 410(38-40):3882-3892 (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 Springer-Verlag Berlin Heidelberg.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.titleExact algorithms for set multicover and multiset multicover problemsen_US
dc.typeConference_Paperen_US
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_US
dc.identifier.authorityLau, FCM=rp00221en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/978-3-642-10631-6_6en_US
dc.identifier.scopuseid_2-s2.0-75649086175en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-75649086175&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume5878 LNCSen_US
dc.identifier.spage34en_US
dc.identifier.epage44en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridHua, QS=15060090400en_US
dc.identifier.scopusauthoridYu, D=30767911100en_US
dc.identifier.scopusauthoridLau, FCM=7102749723en_US
dc.identifier.scopusauthoridWang, Y=35222735000en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats