Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts.
Alexander A. AgeevMaxim SviridenkoPublished in: IPCO (1999)
Keyphrases
- approximation algorithms
- max cut
- np hard
- special case
- worst case
- minimum cost
- primal dual
- graph model
- np complete
- lower bound
- planar graphs
- optimal solution
- branch and bound algorithm
- integer programming
- scheduling problem
- spectral graph
- computational complexity
- linear programming
- constraint satisfaction
- constraint satisfaction problems