3 papers
cs.GT2026
Facility Location Mechanism Design: Breaking The Deterministic Barrier
Zohar Barak
We study the facility location mechanism design problem where agents report their locations in Euclidean space, and the output is a single facility location. The cost function…
cs.DS2026
Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
Zohar Barak, Inbal Talgam-Cohen
In stochastic combinatorial optimization, algorithms differ in their adaptivity: whether or not they query realized randomness and adapt to it. Dean et al. (FOCS '04) formalize the…
cs.GT2026
Approximating Pandora's Knapsack via Simple Policies
Zohar Barak, Asnat Berlin, Ilan Reuven Cohen +3
We introduce Pandora's Knapsack: a hybrid between the classic stochastic knapsack problem [Dean et al., 2008] and Pandora's box [Weitzman, 1979]. As in stochastic knapsack, items h…