TY - GEN
T1 - Submodular clustering in low dimensions
AU - Backurs, Arturs
AU - Har-Peled, Sariel
N1 - Publisher Copyright:
© Arturs Backurs and Sariel Har-Peled; licensed under Creative Commons License CC-BY
PY - 2020/6/1
Y1 - 2020/6/1
N2 - We study a clustering problem where the goal is to maximize the coverage of the input points by k chosen centers. Specifically, given a set of n points P ⊆ Rd, the goal is to pick k centers C ⊆ Rd that maximize the service Pp∈P ϕ(d(p, C)) to the points P, where d(p, C) is the distance of p to its nearest center in C, and ϕ is a non-increasing service function ϕ : R+ → R+. This includes problems of placing k base stations as to maximize the total bandwidth to the clients – indeed, the closer the client is to its nearest base station, the more data it can send/receive, and the target is to place k base stations so that the total bandwidth is maximized. We provide an nε−O(d) time algorithm for this problem that achieves a (1 − ε)-approximation.
AB - We study a clustering problem where the goal is to maximize the coverage of the input points by k chosen centers. Specifically, given a set of n points P ⊆ Rd, the goal is to pick k centers C ⊆ Rd that maximize the service Pp∈P ϕ(d(p, C)) to the points P, where d(p, C) is the distance of p to its nearest center in C, and ϕ is a non-increasing service function ϕ : R+ → R+. This includes problems of placing k base stations as to maximize the total bandwidth to the clients – indeed, the closer the client is to its nearest base station, the more data it can send/receive, and the target is to place k base stations so that the total bandwidth is maximized. We provide an nε−O(d) time algorithm for this problem that achieves a (1 − ε)-approximation.
KW - Covering
KW - PTAS
KW - clustering
UR - http://www.scopus.com/inward/record.url?scp=85090386006&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090386006&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SWAT.2020.8
DO - 10.4230/LIPIcs.SWAT.2020.8
M3 - Conference contribution
AN - SCOPUS:85090386006
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020
A2 - Albers, Susanne
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020
Y2 - 22 June 2020 through 24 June 2020
ER -