81 citations · 310 across the 59 of their papers we have counts for
10 papers · 1 filter
Robust Algorithms for the Secretary Problem
Domagoj Bradac, Anupam Gupta, Sahil Singla +1
In classical secretary problems, a sequence of elements arrive in a uniformly random order, and we want to choose a single item, or a set of size . The random order model al…
The Karger-Stein Algorithm is Optimal for -cut
Anupam Gupta, Euiwoong Lee, Jason Li
In the -cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into connected components. Algorithms…
The Number of Minimum -Cuts: Improving the Karger-Stein Bound
Anupam Gupta, Euiwoong Lee, Jason Li
Given an edge-weighted graph, how many minimum -cuts can it have? This is a fundamental question in the intersection of algorithms, extremal combinatorics, and graph theory. It…
Non-clairvoyant Precedence Constrained Scheduling
Naveen Garg, Anupam Gupta, Amit Kumar +1
We consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are…
Chasing Convex Bodies with Linear Competitive Ratio
C. J. Argue, Anupam Gupta, Guru Guruganesh +1
We study the problem of chasing convex bodies online: given a sequence of convex bodies the algorithm must respond with points in an online…
Tight FPT Approximations for -Median and -Means
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar +2
We investigate the fine-grained complexity of approximating the classical -median / -means clustering problems in general metric spaces. We show how to improve the approximat…