9 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…
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…
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…
A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
Shuchi Chawla, Dimitris Christou, Trung Dang +3
We study multi-buyer multi-item sequential item pricing mechanisms for revenue maximization with the goal of approximating a natural fractional relaxation -- the ex ante optimal re…
Online Time-Windows TSP with Predictions
Shuchi Chawla, Dimitris Christou
In the Time-Windows TSP (TW-TSP) we are given requests at different locations on a network; each request is endowed with a reward and an interval of time; the goal is to find a tou…
Memoryless Algorithms for the Generalized -server Problem on Uniform Metrics
Dimitris Christou, Dimitris Fotakis, Grigorios Koumoutsos
We consider the generalized -server problem on uniform metrics. We study the power of memoryless algorithms and show tight bounds of on their competitive ratio. In parti…
Online learning for min-max discrete problems
Evripidis Bampis, Dimitris Christou, Bruno Escoffier +1
We study various discrete nonlinear combinatorial optimization problems in an online learning framework. In the first part, we address the question of whether there are negative re…