1 citations · 2 across the 15 of their papers we have counts for
18 papers
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…
Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
Thomas Kesselheim, Marco Molinaro, Kalen Patton +1
Online Set Cover and Load Balancing are central problems in online optimization, and there is a long line of work on developing algorithms for these problems with convex objectives…
Improved and Oracle-Efficient Online -Multicalibration
Rohan Ghuge, Vidya Muthukumar, Sahil Singla
We study \emph{online multicalibration}, a framework for ensuring calibrated predictions across multiple groups in adversarial settings, across rounds. Although online calibrat…
Single-Sample and Robust Online Resource Allocation
Rohan Ghuge, Sahil Singla, Yifan Wang
Online Resource Allocation problem is a central problem in many areas of Computer Science, Operations Research, and Economics. In this problem, we sequentially receive stochast…
Online Combinatorial Allocations and Auctions with Few Samples
Paul Dütting, Thomas Kesselheim, Brendan Lucier +2
In online combinatorial allocations/auctions, n bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over subsets of m indivisible items. The a…
Supermodular Approximation of Norms and Applications
Thomas Kesselheim, Marco Molinaro, Sahil Singla
Many classical problems in theoretical computer science involve norm, even if implicitly; for example, both XOS functions and downward-closed sets are equivalent to some norms. The…
Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
Vasilis Livanos, Kalen Patton, Sahil Singla
Over the past two decades, significant strides have been made in stochastic problems such as revenue-optimal auction design and prophet inequalities, traditionally modeled with …
Sample Complexity of Posted Pricing for a Single Item
Billy Jin, Thomas Kesselheim, Will Ma +1
Selling a single item to self-interested buyers is a fundamental problem in economics, where the two objectives typically considered are welfare maximization and revenue maximi…
Robust Disaster Assessment from Aerial Imagery Using Text-to-Image Synthetic Data
Tarun Kalluri, Jihyeon Lee, Kihyuk Sohn +4
We present a simple and efficient method to leverage emerging text-to-image generative models in creating large-scale synthetic supervision for the task of damage assessment from a…
Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems
Danny Segev, Sahil Singla
In this paper, we propose a general framework to design {efficient} polynomial time approximation schemes (EPTAS) for fundamental stochastic combinatorial optimization problems. Gi…