81 citations · 310 across the 59 of their papers we have counts for
11 papers · 1 filter
Online Steiner Tree with Deletions
Anupam Gupta, Amit Kumar
In the online Steiner tree problem, the input is a set of vertices that appear one-by-one, and we have to maintain a Steiner tree on the current set of vertices. The cost of the tr…
Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
Ittai Abraham, Cyril Gavoille, Anupam Gupta +2
We prove that any graph excluding as a minor has can be partitioned into clusters of diameter at most while removing at most fraction of the edges. This improves…
Some Efficient Solutions to Yao's Millionaire Problem
Ashish Kumar, Anupam Gupta
We present three simple and efficient protocol constructions to solve Yao's Millionaire Problem when the parties involved are non-colluding and semi-honest. The first construction…
Towards (1+ε)-Approximate Flow Sparsifiers
Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
A useful approach to "compress" a large network is to represent it with a {\em flow-sparsifier}, i.e., a small network that supports the same flows as , up to a factor $…
Minimum d-dimensional arrangement with fixed points
Anupam Gupta, Anastasios Sidiropoulos
In the Minimum -Dimensional Arrangement Problem (d-dimAP) we are given a graph with edge weights, and the goal is to find a 1-1 map of the vertices into (for some…
Random Rates for 0-Extension and Low-Diameter Decompositions
Anupam Gupta, Kunal Talwar
Consider the problem of partitioning an arbitrary metric space into pieces of diameter at most Δ, such every pair of points is separated with relatively low probability. We propose…