The Library
Streaming facility location in high dimension via geometric hashing
Tools
Tools
Tools
Czumaj, Artur, Jiang, Shaofeng H.-C., Krauthgamer, Robert, Vesely, Pavel and Yang, Mingwei (2022) Streaming facility location in high dimension via geometric hashing. In: The 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022), Denver, CO, USA, 31 Oct - 03 Nov 2022. Published in: Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022) (In Press)
|
PDF
WRAP-Streaming-facility-location-in-high-dimension-via-geometric-hashing-Czumaj-2022.pdf - Accepted Version - Requires a PDF viewer. Download (553Kb) | Preview |
Abstract
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’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 everystreaming1.085-approximation algorithm requires space exponential in poly(d·log ∆), even for insertion-only streams.
| Item Type: | Conference Item (Paper) | ||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||||||||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Computer algorithms, Approximation algorithms, Data structures (Computer science), Data mining -- Mathematical models, Electronic data processing | ||||||||||||||||||||||||||||||||||||
| Journal or Publication Title: | Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022) | ||||||||||||||||||||||||||||||||||||
| Publisher: | IEEE | ||||||||||||||||||||||||||||||||||||
| Official Date: | 2022 | ||||||||||||||||||||||||||||||||||||
| Dates: |
|
||||||||||||||||||||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||||||||||||||||||||
| Publication Status: | In Press | ||||||||||||||||||||||||||||||||||||
| Reuse Statement (publisher, data, author rights): | © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | ||||||||||||||||||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||||||||||||||||||||
| Date of first compliant deposit: | 3 October 2022 | ||||||||||||||||||||||||||||||||||||
| Date of first compliant Open Access: | 3 October 2022 | ||||||||||||||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||||||||||||||||||||
| Conference Paper Type: | Paper | ||||||||||||||||||||||||||||||||||||
| Title of Event: | The 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022) | ||||||||||||||||||||||||||||||||||||
| Type of Event: | Conference | ||||||||||||||||||||||||||||||||||||
| Location of Event: | Denver, CO, USA | ||||||||||||||||||||||||||||||||||||
| Date(s) of Event: | 31 Oct - 03 Nov 2022 | ||||||||||||||||||||||||||||||||||||
| Related URLs: | |||||||||||||||||||||||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
