Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
About this item
Full title
Author / Creator
Publisher
Philadelphia: Society for Industrial and Applied Mathematics
Journal title
Language
English
Formats
Publication information
Publisher
Philadelphia: Society for Industrial and Applied Mathematics
Subjects
More information
Scope and Contents
Contents
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here $\alpha_{\text{\tiny{GW}}} \approx .878567$ denotes the approximation ratio achieved by the algorithm of Goemans and Williamson in [J. Assoc. Comput. Mach.,...
Alternative Titles
Full title
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Authors, Artists and Contributors
Author / Creator
Identifiers
Primary Identifiers
Record Identifier
TN_cdi_proquest_journals_918788617
Permalink
https://devfeature-collection.sl.nsw.gov.au/record/TN_cdi_proquest_journals_918788617
Other Identifiers
ISSN
0097-5397
E-ISSN
1095-7111
DOI
10.1137/S0097539705447372
