11 citations · 48 across the 34 of their papers we have counts for
4 papers · 1 filter
Online Learning with Vector Costs and Bandits with Knapsacks
Thomas Kesselheim, Sahil Singla
We introduce online learning with vector costs (\OLVCp) where in each time step , we need to play an action that incurs an unknown vec…
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
We present a computationally-efficient truthful mechanism for combinatorial auctions with subadditive bidders that achieves an -approximation to the maximum w…
Knapsack Secretary with Bursty Adversary
Thomas Kesselheim, Marco Molinaro
The random-order or secretary model is one of the most popular beyond-worst case model for online algorithms. While it avoids the pessimism of the traditional adversarial model, in…
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
Paul Dütting, Thomas Kesselheim, Brendan Lucier
Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major a…