Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-064 | 6th November 1998 00:00

Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

RSS-Feed

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