52 citations · 58 across the 7 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.DS2022★ 1 cited
A nearly optimal randomized algorithm for explorable heap selection
Sander Borst, Daniel Dadush, Sophie Huiberts +1
Explorable heap selection is the problem of selecting the th smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite b…
math.OC2022★ 52 cited
Integrality Gaps for Random Integer Programs via Discrepancy
Sander Borst, Daniel Dadush, Dan Mikulincer
We prove new bounds on the additive gap between the value of a random integer program with constraints and that of its linear programming…