Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT
| Title | Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT |
| Publication Type | Technical Report |
| Year of Publication | 1997 |
| Authors | W. de la Vega, F., & Karpinski M. |
| Other Numbers | 1121 |
| 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. |
| URL | http://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 |