License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.58
URN: urn:nbn:de:0030-drops-68275
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6827/
Oh, Eunjin ;
Ahn, Hee-Kap
Assigning Weights to Minimize the Covering Radius in the Plane
Abstract
Given a set P of n points in the plane and a multiset W of k weights with k leq n, we assign a weight in W to a point in P to minimize the maximum weighted distance from the weighted center of P to any point in P. In this paper, we give two algorithms which take O(k^2 n^2 log^4 n) time and O(k^5 n log^4 k + kn log^3 n) time, respectively. For a constant k, the second algorithm takes only O(n log^3 n) time, which is near-linear.
BibTeX - Entry
@InProceedings{oh_et_al:LIPIcs:2016:6827,
author = {Eunjin Oh and Hee-Kap Ahn},
title = {{Assigning Weights to Minimize the Covering Radius in the Plane}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {58:1--58:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-026-2},
ISSN = {1868-8969},
year = {2016},
volume = {64},
editor = {Seok-Hee Hong},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6827},
URN = {urn:nbn:de:0030-drops-68275},
doi = {10.4230/LIPIcs.ISAAC.2016.58},
annote = {Keywords: Weighted center, facility location, weight assignment, combinatorial op- timization, computational geometry}
}
|
Keywords: |
|
Weighted center, facility location, weight assignment, combinatorial op- timization, computational geometry |
|
Collection: |
|
27th International Symposium on Algorithms and Computation (ISAAC 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
07.12.2016 |
