Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1997 Copyright 1997 Universität Bonn, Institut für Informatik, Abt. V
8938

Polynomial Time Approximability of Dense Weighted Instances of MAX-CUT
W. Fernandez de la Vega, Marek Karpinski
[Download PostScript] [Download PDF]

We give the first polynomial time approximability characterization of dense weighted instances of MAX-CUT, and some other dense weighted ${\cal NP}$-hard problems in terms of their empirical weight distributions.

Last Change: 11/05/14 at 10:06:14
 English
Universität Bonn -> Institut für Informatik -> Abteilung V