Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

Wenceslas Fernandez de la Vega; Marek Karpinski

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR98-064 | 6th November 1998 00:00

Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

TR98-064 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski
Publication: 6th November 1998 16:03
Downloads: 3682

Keywords:

Approximation Hardness, BISECTION, Computational Complexity, Dense and Non-Dense Weighted Instances, MAX-2SAT, Max-Cut, Polynomial Time Approximation Schemes

Abstract:

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.

ISSN 1433-8092 | Imprint