A Polynomial Time Approximation Scheme for Subdense MAX-CUT
Wenceslas Fernandez de la VegaMarek KarpinskiPublished in: Electron. Colloquium Comput. Complex. (2002)
Keyphrases
- polynomial time approximation
- max cut
- np hard
- approximation algorithms
- error bounds
- lower bound
- optimal solution
- bin packing
- branch and bound algorithm
- computational complexity
- linear programming
- clustering method
- orders of magnitude
- worst case
- scheduling problem
- integer programming
- special case
- np complete problems
- multiscale