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