Streaming Facility Location in High Dimension via Geometric Hashing

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455638" target="_blank" >RIV/00216208:11320/22:10455638 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1109/FOCS54457.2022.00050" target="_blank" >https://doi.org/10.1109/FOCS54457.2022.00050</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/FOCS54457.2022.00050" target="_blank" >10.1109/FOCS54457.2022.00050</a>

Result language

angličtina

Original language name

Streaming Facility Location in High Dimension via Geometric Hashing

Original language description

In Euclidean Uniform Facility Location, the input is a set of clients in Rd and the goal is to place facilities to serve them, so as to minimize the total cost of opening facilities plus connecting the clients. We study the classical setting of dynamic geometric streams, where the clients are presented as a sequence of insertions and deletions of points in the grid {1,. . .,?}d, and we focus on the high-dimensional regime, where the algorithm&apos;s space complexity must be polynomial (and certainly not exponential) in d log ?. We present a new algorithmic framework, based on importance sampling from the stream, for O(1)-approximation of the optimal cost using only poly (d log ?) space. This framework is easy to implement in two passes, one for sampling points and the other for estimating their contribution. Over random-order streams, we can extend this to a one-pass algorithm by using the two halves of the stream separately. Our main result, for arbitrary-order streams, computes O(d1.5)-approximation in one pass by using the new framework but combining the two passes differently. This improves upon previous algorithms that either need space exponential in d or only guarantee O(d log2 ?)-approximation, and therefore our algorithms for high-dimensional streams are the first to avoid the O(log ?) factor in approximation that is inherent to the widely-used quadtree decomposition. Our improvement is achieved by employing a geometric hashing scheme that maps points in Rd into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into at most poly (d) distinct buckets. Finally, we complement our results with a proof that every streaming 1.085-approximation algorithm requires space exponential in poly (d log ?), even for insertion-only streams. © 2022 IEEE.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA22-22997S" target="_blank" >GA22-22997S: Efficient and Realistic Models in Computational Social Choice</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

ISBN

978-1-66545-519-0

ISSN

0272-5428

e-ISSN

—

Number of pages

12

Pages from-to

450-461

Publisher name

IEEE Computer Society

Place of publication

Neuveden

Event location

Denver, USA

Event date

Oct 31, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—