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. Notably, the runtime does not depend on the parameter k and it works for an arbitrary non-increasing service function ϕ : R+ → R+

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. Notably, the runtime does not depend on the parameter k and it works for an arbitrary non-increasing service function ϕ : R+ → R+

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 -