5 papers · 1 filter
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…