限定顶点个数为p的最大割问题的一种近似算法  

An Approximate Method for Max Cut with Given Size of Parts

作　　者：王莲花[1] 刚毅[1] 

机构地区：[1]运城学院应用数学系,山西运城044000

出　　处：《山西大同大学学报（自然科学版）》2008年第6期7-9,共3页Journal of Shanxi Datong University(Natural Science Edition)

基　　金：运城学院科研项目[20060217]

摘　　要：给出了求解限定顶点个数为p的最大割问题的一种近似算法,讨论了它的性能保证,利用Pipage技术,为最大割问题设计出了0.5-近似算法.A new approximate method is presented for max cut with given size of parts, and its performance guarantee is analysed. By using the Pipage technique , a 0.5-approximate algorithm is presented.

关 键 词：最大割近似算法 ε-凸性 

分 类 号：O122[理学—数学]