6 papers · 1 filter
Universal Algorithms for Clustering Problems
Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi
This paper presents universal algorithms for clustering problems, including the widely studied -median, -means, and -center objectives. The input is a metric space contain…
Privately Answering Counting Queries with Generalized Gaussian Mechanisms
Arun Ganesh, Jiazheng Zhao
We consider the problem of answering counting (i.e. sensitivity-1) queries about a database with -differential privacy. We give a mechanism such that if the true answer…
Near-Linear Time Edit Distance for Indel Channels
Arun Ganesh, Aaron Sy
We consider the following model for sampling pairs of strings: is a uniformly random bitstring of length , and is the bitstring arrived at by applying substitutions,…
Robust Algorithms for TSP and Steiner Tree
Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the e…
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh, Qiuyi Zhang
We consider the phylogenetic tree reconstruction problem with insertions and deletions (indels). Phylogenetic algorithms proceed under a model where sequences evolve down the model…
Online Service with Delay
Yossi Azar, Arun Ganesh, Rong Ge +1
In this paper, we introduce the online service with delay problem. In this problem, there are points in a metric space that issue service requests over time, and a server that…