Premium
Polynomial time approximation of dense weighted instances of MAX‐CUT
Author(s) -
Fernandez de la Vega W.,
Karpinski M.
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200007)16:4<314::aid-rsa2>3.0.co;2-e
Subject(s) - mathematics , combinatorics , polynomial , discrete mathematics , mathematical analysis
We give the first polynomial time approximability characterization of denseweighted instances of MAX‐CUT, and some other dense weighted ‐hard problems in terms of their empirical weight distributions. This also gives the first almost sharp characterization of inapproximability of unweighted 0, 1 MAX‐BISECTION instances in terms of their density parameter. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 314–332, 2000