research
∙
07/15/2023
Fully Scalable MPC Algorithms for Clustering in High Dimension
We design new algorithms for k-clustering in high-dimensional Euclidean ...
share
research
∙
04/05/2022
Streaming Facility Location in High Dimension via New Geometric Hashing
In Euclidean Uniform Facility Location, the input is a set of clients in...
research
∙
11/06/2021
Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
In the Shortest Superstring problem, we are given a set of strings and w...
research
∙
02/18/2021
Theory meets Practice at the Median: a worst case comparison of relative error quantile algorithms
Estimating the distribution and quantiles of data is a foundational task...
research
∙
12/07/2020
Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
We consider the problem of managing the buffer of a shared-memory switch...
research
∙
11/09/2020
Streaming Algorithms for Geometric Steiner Forest
We consider a natural generalization of the Steiner tree problem, the St...
research
∙
04/03/2020
Relative Error Streaming Quantiles
Approximating ranks, quantiles, and distributions over streaming data is...
research
∙
05/13/2019
Streaming Algorithms for Bin Packing and Vector Scheduling
Problems involving the efficient arrangement of simple objects, as captu...
research
∙
05/09/2019
Tight Lower Bound for Comparison-Based Quantile Summaries
Quantiles, such as the median or percentiles, provide concise and useful...
research
∙
07/18/2018
A φ-Competitive Algorithm for Scheduling Packets with Deadlines
In the online packet scheduling problem with deadlines (PacketScheduling...
research
∙
10/02/2017
