A Logarithmic Additive Integrality Gap for Bin Packing

Rebecca Hoberg, Thomas Rothvoss

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. Recently, the second author gav…