Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOUNDED MAX-CSP:
Reports tagged with Bounded MAX-CSP:
TR00-021 | 19th April 2000
Uriel Feige, Marek Karpinski, Michael Langberg

#### Improved Approximation of MAX-CUT on Graphs of Bounded Degree

We analyze the addition of a simple local improvement step to various known
randomized approximation algorithms.
Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently
known for the Max Cut problem on general graphs~\cite{GW95}.
We consider a semidefinite relaxation of the Max Cut problem,
round it using the ... more >>>

ISSN 1433-8092 | Imprint