Local approximation algorithms for a class of 0/1 max-min linear programs
Patrik FloréenMarja HassinenPetteri KaskiJukka SuomelaPublished in: CoRR (2008)
Keyphrases
- approximation algorithms
- linear program
- max min
- np hard
- primal dual
- linear programming
- special case
- vertex cover
- min max
- worst case
- minimum cost
- optimal solution
- approximation ratio
- simplex method
- lower bound
- convex functions
- objective function
- network design problem
- column generation
- mixed integer
- combinatorial auctions
- integer programming
- dynamic programming
- computational complexity
- search algorithm
- constant factor
- evolutionary algorithm
- semidefinite programming
- branch and bound algorithm
- search space
- robust optimization