38 citations · 157 across the 44 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021
Online metric allocation
Nikhil Bansal, Christian Coester
We introduce a natural online allocation problem that connects several of the most fundamental problems in online optimization. Let be an -point metric space. Consider a res…
cs.DS2021
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 $…
cs.DM2021★ 2 cited
The Power of Two Choices in Graphical Allocation
Nikhil Bansal, Ohad Feldheim
The graphical balls-into-bins process is a generalization of the classical 2-choice balls-into-bins process, where the bins correspond to vertices of an arbitrary underlying graph…