7 citations · 20 across the 9 of their papers we have counts for
8 papers · 1 filter
Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7
In linear combinatorial optimization, we aim to find for a family over a ground set…
Dimension-Free Bounds on Chasing Convex Functions
C. J. Argue, Anupam Gupta, Guru Guruganesh
We consider the problem of chasing convex functions, where functions arrive over time. The player takes actions after seeing the function, and the goal is to achieve a small functi…
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…
Stochastic Online Metric Matching
Anupam Gupta, Guru Guruganesh, Binghui Peng +1
We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive onl…
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh +3
Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rou…
Understanding the Correlation Gap for Matchings
Guru Guruganesh, Euiwoong Lee
Given a set of vertices with , a weight vector , and a probability vector in the matchi…