5 papers
A Simple Algorithm for Counting Solutions to Integer Programs
Daniel Dadush, Anita Dürr, Thekla Hamm +2
We consider the problem of counting solutions to integer linear programming problems of the form where $A \in \{-Δ,\ldots,Δ\}^{m \times n…
Greedy Vector Balancing
Wojciech Czerwiński, Daniel Dadush, Ekin Ergen +3
In online vector balancing, vectors arrive one by one from a given set and the goal is to assign signs in an online manner so as to m…
Revisiting Diameter in Directed Graphs
Ben Bals, Joakim Blikstad, Daniel Dadush +2
The reachability diameter () of a directed graph is the maximum distance over all pairs where is reachable from . This notion is present in the def…
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
Lower bounds for cube-ideal set-systems
Ahmad Abdi, Gérard Cornuéjols, Daniel Dadush +1
A set-system is cube-ideal if its convex hull can be described by capacity and generalized set covering inequalities. In this paper, we use combinatorics, co…