38 citations · 157 across the 44 of their papers we have counts for
6 papers · 1 filter
Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
Nikhil Bansal, Shashwat Garg, Jesper Nederlof +1
We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with items using time and polynomial space, where the $O^*(\cdot…
Algorithmic Discrepancy Beyond Partial Coloring
Nikhil Bansal, Shashwat Garg
The partial coloring method is one of the most powerful and widely used method in combinatorial discrepancy problems. However, in many cases it leads to sub-optimal bounds as the p…
The -Server Problem on Bounded Depth Trees
Nikhil Bansal, Marek Eliáš, Łukasz Jeż +1
We study the -server problem in the resource augmentation setting i.e., when the performance of the online algorithm with servers is compared to the offline optimal solution…
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
Nikhil Bansal, Daniel Reichman, Seeun William Umboh
We give a general approach for solving optimization problems on noisy minor free graphs, where a δ-fraction of edges and vertices are adversarially corrupted. The noisy setting was…
An Algorithm for Komlós Conjecture Matching Banaszczyk's bound
Nikhil Bansal, Daniel Dadush, Shashwat Garg
We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring…
Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems
Nikhil Bansal, Shashwat Garg
We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most sets. We give an algorithm that finds a coloring with di…