Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with BISECTION:
TR98-064 | 6th November 1998
Wenceslas Fernandez de la Vega, Marek Karpinski

Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

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 ... more >>>

ISSN 1433-8092 | Imprint