Publication Details
Title: Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT
Author: W. Fernandez de la Vega and M. Karpinski
Group: ICSI Technical Reports
Date: December 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-059.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-97-059
Bibliographic Reference:
W. Fernandez de la Vega and M. Karpinski. Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT. ICSI Technical Report TR-97-059, December 1997
Author: W. Fernandez de la Vega and M. Karpinski
Group: ICSI Technical Reports
Date: December 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-059.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-97-059
Bibliographic Reference:
W. Fernandez de la Vega and M. Karpinski. Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT. ICSI Technical Report TR-97-059, December 1997