Thomas Rothvoss

In a seminal paper, Kannan and Lovász (1988) considered a quantity µ K L ( Λ , K ) which denotes the best volume-based lower bound on the covering radius µ ( Λ , K ) of a convex body K with respect to a lattice Λ . Kannan and Lovász proved that µ ( Λ...

For bin packing, the input consists of n items with sizes s_1,...,s_n in [0,1] which have to be assigned to a minimum number of bins of size 1. The seminal Karmarkar-Karp algorithm from 1982 produces a solution with at most OPT + O(log^2 OPT) bins in...