1 citations · 2 across the 15 of their papers we have counts for
9 papers · 1 filter
Improved Combinatorial Auctions with and without Samples
Aviad Rubinstein, Sahil Singla
We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare ma…
Efficient Algorithms for Online Subadditive Combinatorial Allocations
Calum MacRury, Rian Neogi, Kanstantsin Pashkovich +4
For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a -competitive online algorithm, improving on…
The Cube-Root Phenomenon in Online Carpooling
Nikhil Bansal, Milind Prabhu, Sahil Singla +1
We consider the online carpooling problem, where edges arrive online and must be oriented immediately while keeping the discrepancy between the indegree and outdegree at each verte…
Online Allocation using Few Samples
Matthew Faw, Sahil Singla, Yifan Wang
We study online allocation problems where requests over resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures bot…
Adversarial Online Classification with a Preview
Roi Livni, Sahil Singla
Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as threshold…
Online Algorithms via Minimax and Posterior Matching
Thomas Kesselheim, Marco Molinaro, Kalen Patton +1
Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpo…
Philosopher and Prophet Inequalities for Divisible Items
Thiago Oliveira, Mohit Singh, Sahil Singla
We study online welfare maximization with divisible resources. A sequence of players arrive one by one; upon arrival, each player draws a valuation function over divisible…
Online Graph Balancing and the Power of Two Choices
Nikhil Bansal, Milind Prabhu, Sahil Singla +1
In the classic online graph balancing problem, edges arrive sequentially and must be oriented immediately upon arrival, to minimize the maximum in-degree. For adversarial arrivals,…
Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
Aviad Rubinstein, Sahil Singla
We revisit three fundamental problems in algorithms under uncertainty: the Secretary Problem, Prophet Inequality, and Stochastic Probing, each subject to general downward-closed co…