File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Set multi-covering via inclusion-exclusion

TitleSet multi-covering via inclusion-exclusion
Authors
KeywordsAlgorithm
Complexity
Inclusion-exclusion
Set multi-covering
Issue Date2009
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2009, v. 410 n. 38-40, p. 3882-3892 How to Cite?
AbstractSet multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion-exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O* ((2 t)n) time and O* ((t + 1)n) space where t is the maximum value in the coverage requirement set (The O* (f (n)) notation omits a p o l y log (f (n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion-exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)]. © 2009 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/65467
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
ISI Accession Number ID
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-10T00:57:34Z-
dc.date.available2010-08-10T00:57:34Z-
dc.date.issued2009en_HK
dc.identifier.citationTheoretical Computer Science, 2009, v. 410 n. 38-40, p. 3882-3892en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/65467-
dc.description.abstractSet multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion-exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O* ((2 t)n) time and O* ((t + 1)n) space where t is the maximum value in the coverage requirement set (The O* (f (n)) notation omits a p o l y log (f (n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion-exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)]. © 2009 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.rightsTheoretical Computer Science. Copyright © Elsevier BV.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectAlgorithmen_HK
dc.subjectComplexityen_HK
dc.subjectInclusion-exclusionen_HK
dc.subjectSet multi-coveringen_HK
dc.titleSet multi-covering via inclusion-exclusionen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=410&issue=38-40&spage=3882&epage=3892&date=2009&atitle=Set+multi-covering+via+inclusion-exclusion-
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1016/j.tcs.2009.05.020en_HK
dc.identifier.scopuseid_2-s2.0-68249120272en_HK
dc.identifier.hkuros172268-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-68249120272&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume410en_HK
dc.identifier.issue38-40en_HK
dc.identifier.spage3882en_HK
dc.identifier.epage3892en_HK
dc.identifier.isiWOS:000269683400028-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridHua, QS=15060090400en_HK
dc.identifier.scopusauthoridWang, Y=7601522106en_HK
dc.identifier.scopusauthoridYu, D=30767911100en_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK
dc.identifier.citeulike5089736-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats