14 citations · 21 across the 20 of their papers we have counts for
4 papers · 1 filter
Local search breaks 1.75 for Graph Balancing
Klaus Jansen, Lars Rohwedder
Graph Balancing is the problem of orienting the edges of a weighted multigraph so as to minimize the maximum weighted in-degree. Since the introduction of the problem the best algo…
Near-Linear Time Algorithm for n-fold ILPs via Color Coding
Klaus Jansen, Alexandra Lassota, Lars Rohwedder
We study an important case of ILPs with variables and lower and upper bounds $\ell,…
A note on the integrality gap of the configuration LP for restricted Santa Claus
Klaus Jansen, Lars Rohwedder
In the restricted Santa Claus problem we are given resources and players . Every resource has a value and every player desires a…
On Integer Programming, Discrepancy, and Convolution
Klaus Jansen, Lars Rohwedder
Integer programs with m constraints are solvable in pseudo-polynomial time in , the largest coefficient in a constraint, when m is a fixed constant. We give a new algorithm with…