5 citations · 17 across the 12 of their papers we have counts for
19 papers · 1 filter
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…
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 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…