8 papers
Stochastic Weighted Caching with Per-Request Predictions
Shuchi Chawla, Dimitris Christou
Both the unweighted and weighted variants of caching are cornerstone problems in competitive analysis, with tight randomized competitive ratios of , where is the cac…
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Dimitris Christou, Jiayi Chen, Nihal Sharma +3
Modern inference systems rely on batching to exploit parallel execution and amortize serial execution overheads, but batching creates a fundamental online scheduling tradeoff: serv…
Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction
Shuchi Chawla, Trung Dang
We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities…
Pricing Pandora's Boxes: Revenue Maximization in Sequential Information Acquisition
Shuchi Chawla, Dimitris Christou, Trung Dang +1
We study a mechanism design problem in which a seller controls access to information about a set of stochastic alternatives, and a buyer sequentially acquires information in order…
Bi-Lipschitz extensions and outlier embeddings into trees
Shuchi Chawla, Arnold Filtser, Kristin Sheridan +1
We develop low distortion embeddings with outliers from arbitrary metrics into hierarchically separated trees (HSTs). In particular, we develop an efficient algorithm that for any…
Commitment Gap via Correlation Gap
Shuchi Chawla, Dimitris Christou, Trung Dang
Selection problems with costly information, dating back to Weitzman's Pandora's Box problem, have received much attention recently. We study the general model of Costly Information…
Combinatorial Selection with Costly Information
Shuchi Chawla, Dimitris Christou, Amit Harlev +1
We consider a class of optimization problems over stochastic variables where the algorithm can learn information about the value of any variable through a series of costly steps; w…
Faster feasibility for dynamic flows and transshipments on temporal networks
Kristin Sheridan, Shuchi Chawla
In this paper we study flow problems on temporal networks, where edge capacities and travel times change over time. We consider a network with nodes and edges where the cap…