12 citations · 55 across the 25 of their papers we have counts for
36 papers
The Matroid Secretary Conjecture is True
Sahil Singla
We resolve the matroid secretary conjecture, giving an online algorithm that accepts each element of the offline optimum with probability at least . The algorithm only needs t…
Submodular Norms with Applications To Online Facility Location and Stochastic Probing
Kalen Patton, Matteo Russo, Sahil Singla
Optimization problems often involve vector norms, which has led to extensive research on developing algorithms that can handle objectives beyond the norms. Our work introd…
Bandit Algorithms for Prophet Inequality and Pandora's Box
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla +1
The Prophet Inequality and Pandora's Box problems are fundamental stochastic problem with applications in Mechanism Design, Online Algorithms, Stochastic Optimization, Optimal Stop…
Submodular Dominance and Applications
Frederick Qiu, Sahil Singla
In submodular optimization we often deal with the expected value of a submodular function on a distribution over sets of elements. In this work we study such subm…
Smoothed Analysis of the Komlós Conjecture
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
The well-known Komlós conjecture states that given vectors in with Euclidean norm at most one, there always exists a coloring such that the $\ell_{\infty…
Robust Secretary and Prophet Algorithms for Packing Integer Programs
C. J. Argue, Anupam Gupta, Marco Molinaro +1
We study the problem of solving Packing Integer Programs (PIPs) in the online setting, where columns in of the constraint matrix are revealed sequentially, and the goal i…
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
A well-known result of Banaszczyk in discrepancy theory concerns the prefix discrepancy problem (also known as the signed series problem): given a sequence of unit vectors in $…
Online Discrepancy with Recourse for Vectors and Graphs
Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy +2
The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in , find a signing of each vector to minimize the d…
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla +1
Babaioff et al. [BIK2007] introduced the matroid secretary problem in 2007, a natural extension of the classic single-choice secretary problem to matroids, and conjectured that a c…
Bag-of-Tasks Scheduling on Related Machines
Anupam Gupta, Amit Kumar, Sahil Singla
We consider online scheduling to minimize weighted completion time on related machines, where each job consists of several tasks that can be concurrently executed. A job gets compl…
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…
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, Sahil Singla +1
We consider an online vector balancing question where vectors, chosen from an arbitrary distribution over , arrive one-by-one and must be immediately given a si…
Robust Algorithms for the Secretary Problem
Domagoj Bradac, Anupam Gupta, Sahil Singla +1
In classical secretary problems, a sequence of elements arrive in a uniformly random order, and we want to choose a single item, or a set of size . The random order model al…
Faster Matroid Intersection
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford +2
In this paper we consider the classic matroid intersection problem: given two matroids $\M_{1}=(V,\I_{1})$ and $\M_{2}=(V,\I_{2})$ defined over a common ground set , compute a s…
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
Sepehr Assadi, Sahil Singla
A longstanding open problem in Algorithmic Mechanism Design is to design computationally-efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial aucti…
Algorithms and Adaptivity Gaps for Stochastic -TSP
Haotian Jiang, Jian Li, Daogao Liu +1
Given a metric and a , the classic $\textsf{$k$-TSP}$ problem is to find a tour originating at the of minimum length that visits at lea…
Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization
Haotian Jiang, Janardhan Kulkarni, Sahil Singla
Consider a unit interval in which points arrive one-by-one independently and uniformly at random. On arrival of a point, the problem is to immediately and irrevocably c…
Non-clairvoyant Precedence Constrained Scheduling
Naveen Garg, Anupam Gupta, Amit Kumar +1
We consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are…
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries
Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman +2
We consider a revenue-maximizing seller with items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distin…