22 citations · 121 across the 43 of their papers we have counts for
17 papers · 1 filter
A General Framework for Matching with Delays
Sara Ahmadian, Shuchi Chawla, Ravi Kumar +2
We present a simple deterministic -competitive algorithm for the online minimum-cost perfect matching with delays (MPMD) problem on arbitrary, unknown metric spaces, whe…
Multi-Level Aggregation via Dual Fitting: An -Competitive Algorithm
Sara Ahmadian, Shuchi Chawla, Ravi Kumar +2
We present a new online algorithm for the well-known Multi-Level Aggregation Problem (MLAP) with arbitrary delay functions, achieving a -competitive ratio, where is the dep…
Composition of nested embeddings with an application to outlier removal
Shuchi Chawla, Kristin Sheridan
We study the design of embeddings into Euclidean space with outliers. Given a metric space and an integer , the goal is to embed all but points in (called the ``…
Online Time-Windows TSP with Predictions
Shuchi Chawla, Dimitris Christou
In the Time-Windows TSP (TW-TSP) we are given requests at different locations on a network; each request is endowed with a reward and an interval of time; the goal is to find a tou…
Approximating Pandora's Box with Correlations
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan +1
We revisit the classic Pandora's Box (PB) problem under correlated distributions on the box values. Recent work of arXiv:1911.01632 obtained constant approximate algorithms for a r…
Non-Adaptive Matroid Prophet Inequalities
Shuchi Chawla, Kira Goldner, Anna R. Karlin +1
We investigate non-adaptive algorithms for matroid prophet inequalities. Matroid prophet inequalities have been considered resolved since 2012 when [KW12] introduced thresholds tha…