Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

TitlePolynomial Time Approximation of Dense Weighted Instances of MAX-CUT
Publication TypeTechnical Report
Year of Publication1997
AuthorsW. de la Vega, F., & Karpinski M.
Other Numbers1121
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 char acterization of inapproximability of unweighted 0,1 MAX-BISECTION instances in terms of their density parameter only.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1997/tr-97-059.pdf
Bibliographic Notes

ICSI Technical Report TR-97-059

Abbreviated Authors

W. Fernandez de la Vega and M. Karpinski

ICSI Publication Type

Technical Report