5 citations · 26 across the 18 of their papers we have counts for
8 papers · 2 filters
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…
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…