1 citations · 2 across the 15 of their papers we have counts for
10 papers · 1 filter
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…
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…
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…
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…
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…