12 citations · 55 across the 25 of their papers we have counts for
6 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…
Online Discrepancy Minimization for Stochastic Arrivals
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
In the stochastic online vector balancing problem, vectors chosen independently from an arbitrary distribution in arrive one-by-one and must be…
Online Carpooling using Expander Decompositions
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar +1
We consider the online carpooling problem: given vertices, a sequence of edges arrive over time. When an edge arrives at time step , the algorithm must or…
Random-Order Models
Anupam Gupta, Sahil Singla
This chapter introduces the \emph{random-order model} in online algorithms. In this model, the input is chosen by an adversary, then randomly permuted before being presented to the…
Prophet Inequalities with Linear Correlations and Augmentations
Nicole Immorlica, Sahil Singla, Bo Waggoner
In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distribut…