A Logarithmic Additive Integrality Gap for Bin Packing.
Rebecca HobergThomas RothvossPublished in: SODA (2017)
Keyphrases
- bin packing
- integrality gap
- linear programming relaxation
- linear program
- worst case
- lower bound
- approximation algorithms
- arbitrarily close
- valid inequalities
- graph colouring
- packing problem
- knapsack problem
- lp relaxation
- integer programming formulation
- linear programming
- search tree
- low degree
- integer programming
- primal dual
- multi dimensional
- np hard
- mixed integer programming
- mixed integer
- column generation
- finite number
- distributed systems