【摘要】 给出了求解给定部分大小的最大有向割问题的一种新的近似方法,并讨论了它的性能保证.该方法的核心是利用Pipage技术,并结合线性松驰的基本解的特性,为给定部分大小的最大有向割问题设计出了0.5-近似算法.更多还原

【Abstract】 A new approximate method is presented for max dicut problem with given size of the parts,and its performance guarantee is analysed.The core of the method is the technique based on exploiting structure properties of basic solutions to a linear relaxation.By using the method,a approximate algorithm is presented.更多还原