On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem.
Mong-Jen KaoPublished in: SODA (2023)
Keyphrases
- integrality gap
- linear programming relaxation
- linear program
- arbitrarily close
- tight upper and lower bounds
- lower bound
- approximation algorithms
- lp relaxation
- linear programming
- knapsack problem
- valid inequalities
- optimal solution
- feasible solution
- primal dual
- branch and bound
- traveling salesman problem
- np hard
- integer programming formulation
- upper bound
- mixed integer programming
- finite number
- integer programming
- np hardness
- low degree
- greedy algorithm
- column generation
- semi definite programming
- search algorithm
- objective function