Submodular clustering in low dimensions

Arturs Backurs, Sariel Har-Peled

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 PpP ϕ(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+

Original languageEnglish (US)
Title of host publication17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020
EditorsSusanne Albers
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771504
DOIs
StatePublished - Jun 1 2020
Event17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020 - Torshavn, Faroe Islands
Duration: Jun 22 2020Jun 24 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume162
ISSN (Print)1868-8969

Conference

Conference17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020
Country/TerritoryFaroe Islands
CityTorshavn
Period6/22/206/24/20

Keywords

  • clustering
  • Covering
  • PTAS

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Submodular clustering in low dimensions'. Together they form a unique fingerprint.

Cite this