4 papers
Ex-ante versus Ex-post: Egalitarian Facility Location Mechanism Design
Zohar Barak, Inbal Talgam-Cohen
We study the facility location mechanism design problem where strategic agents report locations in Euclidean space and the mechanism outputs a single facility location. Each ag…
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…
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…
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…