60 citations · 269 across the 42 of their papers we have counts for
10 papers · 1 filter
The Strong Secretary Conjecture is True for Linear Matroids
Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos +2
We prove a guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both…
Batched Pandora's Box
Shaddin Dughmi, Yusuf Hakan Kalayci, Vasilis Livanos +1
Motivated by numerous parallelizable stochastic search problems, most notable and timely among them being LLM inference-time scaling, we propose and study batched versions of the P…
Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu
When uncertainty meets costly information gathering, a fundamental question emerges: which data points should we probe to unlock near-optimal solutions? Sparsification of stochasti…
Limitations of Stochastic Selection with Pairwise Independent Priors
Shaddin Dughmi, Yusuf Hakan Kalayci, Neel Patel
Motivated by the growing interest in correlation-robust stochastic optimization, we investigate stochastic selection problems beyond independence. Specifically, we consider the ins…
On Sparsification of Stochastic Packing Problems
Shaddin Dughmi, Yusuf Hakan Kalayci, Neel Patel
Motivated by recent progress on stochastic matching with few queries, we embark on a systematic study of the sparsification of stochastic packing problems (SPP) more generally. Spe…
Matroid Secretary Is Equivalent to Contention Resolution
Shaddin Dughmi
We show that the matroid secretary problem is equivalent to correlated contention resolution in the online random-order model. Specifically, the matroid secretary conjecture is tru…