文章基本信息

标题：Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT
本地全文：下载
作者：Wenceslas Fernandez de la Vega ; Marek Karpinski
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give the first polynomial time approximability characterization of dense weighted instances of MAX-CUT, and some other dense weighted NP-hard problems in terms of their empirical weight distributions. This gives also the first almost sharp characterization of inapproximability of unweighted 0,1 MAX-BISECTION instances in terms of their density parameter.
关键词：Approximation Hardness, BISECTION, Computational Complexity, Dense and Non-Dense Weighted Instances, MAX-2SAT, Max-Cut, Polynomial Time Approximation Schemes Abstract: