38 citations · 157 across the 44 of their papers we have counts for
4 papers · 1 filter
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…
Non-uniform Geometric Set Cover and Scheduling on Multiple Machines
Nikhil Bansal, Jatin Batra
We consider the following general scheduling problem studied recently by Moseley. There are jobs, all released at time , where job has size and an associated arbit…
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
Nikhil Bansal, Ola Svensson, Luca Trevisan
A sparsifier of a graph (Benczúr and Karger; Spielman and Teng) is a sparse weighted subgraph that approximately retains the cut structure of . For general graphs…
On-Line Balancing of Random Inputs
Nikhil Bansal, Joel H. Spencer
We consider an online vector balancing game where vectors , chosen uniformly at random in , arrive over time and a sign must be picked immedia…