File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Near-linear time approximation schemes for geometric maximum coverage

TitleNear-linear time approximation schemes for geometric maximum coverage
Authors
KeywordsMaximum coverage
Geometric set cover
Polynomial-time approximation scheme
Issue Date2018
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2018, v. 725, p. 64-78 How to Cite?
AbstractWe study approximation algorithms for the following geometric version of the maximum coverage problem: Let be a set of n weighted points in the plane. Let D represent a planar object, such as a rectangle, or a disk. We want to place m copies of D such that the sum of the weights of the points in covered by these copies is maximized. For any fixed , we present efficient approximation schemes that can find a -approximation to the optimal solution. In particular, for and for the special case where D is a rectangle, our algorithm runs in time , improving on the previous result. For and the rectangular case, our algorithm runs in time. For a more general class of shapes (including disks, polygons with edges), our algorithm runs in time.
Persistent Identifierhttp://hdl.handle.net/10722/259910
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorJin, K-
dc.contributor.authorLi, J-
dc.contributor.authorWang, H-
dc.contributor.authorZhang, B-
dc.contributor.authorZhang, N-
dc.date.accessioned2018-09-03T04:16:20Z-
dc.date.available2018-09-03T04:16:20Z-
dc.date.issued2018-
dc.identifier.citationTheoretical Computer Science, 2018, v. 725, p. 64-78-
dc.identifier.issn0304-3975-
dc.identifier.urihttp://hdl.handle.net/10722/259910-
dc.description.abstractWe study approximation algorithms for the following geometric version of the maximum coverage problem: Let be a set of n weighted points in the plane. Let D represent a planar object, such as a rectangle, or a disk. We want to place m copies of D such that the sum of the weights of the points in covered by these copies is maximized. For any fixed , we present efficient approximation schemes that can find a -approximation to the optimal solution. In particular, for and for the special case where D is a rectangle, our algorithm runs in time , improving on the previous result. For and the rectangular case, our algorithm runs in time. For a more general class of shapes (including disks, polygons with edges), our algorithm runs in time.-
dc.languageeng-
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs-
dc.relation.ispartofTheoretical Computer Science-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectMaximum coverage-
dc.subjectGeometric set cover-
dc.subjectPolynomial-time approximation scheme-
dc.titleNear-linear time approximation schemes for geometric maximum coverage-
dc.typeArticle-
dc.identifier.emailJin, K: cskaijin@hku.hk-
dc.description.naturepostprint-
dc.identifier.doi10.1016/j.tcs.2017.11.026-
dc.identifier.scopuseid_2-s2.0-85036537756-
dc.identifier.hkuros289840-
dc.identifier.volume725-
dc.identifier.spage64-
dc.identifier.epage78-
dc.identifier.isiWOS:000430785700005-
dc.publisher.placeNetherlands-
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats