LP-based Approximation Algorithms for Capacitated Facility Location.
Retsef LeviDavid B. ShmoysChaitanya SwamyPublished in: IPCO (2004)
Keyphrases
- facility location
- approximation algorithms
- np hard
- integer programming
- multi commodity
- linear programming
- facility location problem
- lagrangian relaxation
- primal dual
- mixed integer
- linear program
- special case
- vertex cover
- network design problem
- optimal solution
- worst case
- minimum cost
- lp relaxation
- network design
- np complete
- scheduling problem
- constant factor
- lower bound
- approximation ratio
- column generation
- integrality gap
- computational complexity
- valid inequalities
- lot sizing
- production planning
- branch and bound algorithm
- constraint satisfaction problems
- mixed integer programming
- multi criteria
- linear programming relaxation
- vehicle routing problem
- network flow problem
- convex hull
- multi objective