Experimental Analysis of Approximation Algorithms for the Vertex Cover and Set Covering Problems.
Fernando C. GomesCláudio Nogueira de MenesesPanos M. PardalosGerardo Valdisio R. VianaPublished in: Comput. Oper. Res. (2006)
Keyphrases
- vertex cover
- approximation algorithms
- set covering problem
- np hard
- branch and bound algorithm
- set covering
- integer programming
- special case
- column generation
- worst case
- minimum cost
- combinatorial auctions
- precedence constraints
- approximation ratio
- linear programming
- polynomial time approximation
- constant factor
- lower bound
- branch and bound
- np complete
- simulated annealing
- upper bound
- scheduling problem