10 citations · 23 across the 8 of their papers we have counts for
5 papers · 1 filter
Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem
Stephen R. Chestnut, Robert Hildebrand, Rico Zenklusen
The recent paper "A quantitative Doignon-Bell-Scarf Theorem" by Aliev et al. generalizes the famous Doignon-Bell-Scarf Theorem on the existence of integer solutions to systems of l…
Hardness and Approximation for Network Flow Interdiction
Stephen R. Chestnut, Rico Zenklusen
In the Network Flow Interdiction problem an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem…
Interdicting Structured Combinatorial Optimization Problems with {0,1}-Objectives
Stephen R. Chestnut, Rico Zenklusen
Interdiction problems ask about the worst-case impact of a limited change to an underlying optimization problem. They are a natural way to measure the robustness of a system, or to…
Beating CountSketch for Heavy Hitters in Insertion Streams
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin +1
Given a stream of items from a universe , which, without loss of generality we identify with the set of integers , we consider…
Streaming Symmetric Norms via Measure Concentration
Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut +2
We characterize the streaming space complexity of every symmetric norm (a norm on invariant under sign-flips and coordinate-permutations), by relating this space…