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

An Approximate Method for Max Cut with Given Size of Parts

给出了求解限定顶点个数为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.