首页   按字顺浏览 期刊浏览 卷期浏览 A cutting plane algorithm for the max-cut problem*
A cutting plane algorithm for the max-cut problem*

 

作者: C. De Simone,   G. Rinaldi,  

 

期刊: Optimization Methods and Software  （Taylor Available online 1994）
卷期: Volume 3, issue 1-3  

页码: 195-214

 

ISSN:1055-6788

 

年代: 1994

 

DOI:10.1080/10556789408805564

 

出版商: Gordon and Breach Science Publishers

 

关键词: Polyhedral Combinatorics;Separation Problem;Maximum Cut Problem;Hypermetric Inequality

 

数据来源: Taylor

 

摘要:

In this paper we describe a cutting plane algorithm to solve max-cut problems on complete graphs. We show that the separation problem over the cut polytope can be reduced to the separation problem over the cut cone and we give a separation algorithm for a class of inequalities valid over the cut cone:the hypermetric inequalities.Computational results are given.

 

点击下载:  PDF (589KB)



返 回