Complexity results for the gap inequalities for the max-cut problem

详细信息	查看全文 | 推荐本文 |

• 作者：Laura Galli^a ; ^{l.galli@unibo.it} ; Konstantinos Kaparis^b ; ^{K.Kaparis@lancaster.ac.uk} ; Adam N. Letchford^b ; ^{A.N.Letchford@lancaster.ac.uk}
• 关键词：Computational complexity ; Max-cut problem ; Cutting planes
• 刊名：Operations Research Letters
• 出版年：2012
• 期刊代码：134_01676377
• 类别：et
• 出版时间：May, 2012
• 卷：40
• 期：3
• 页码：149-152
• 文件大小：239 K

摘要

We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap- inequalities do not imply the other gap inequalities, unless Co ; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless Co ; (iii) the associated separation problem can be solved in finite (doubly exponential) time.