Skip to main content
added 35 characters in body
Source Link

In the article "Approximate Max Cut" by S. Har-Peled, the last line of the paper mentioned that the real weighted version of max-cut has been discussed in

Approximating the cut-norm via grothendieck’s inequality, Noga Alon and Assaf Naor, SIAM Journal on Computing, 2006.

It is indeed an SDP algorithm, and it seems to me that the approximation ratio is 0.56, though I'm not sure if the reduction discussed in the paper is ratio preserving. Maybe a deeper look into the paper will help!

In the article "Approximate Max Cut" by S. Har-Peled, the last line of the paper mentioned that the real weighted version of max-cut has been discussed in

Approximating the cut-norm via grothendieck’s inequality, Noga Alon and Assaf Naor, SIAM Journal on Computing, 2006.

It seems to me that the approximation ratio is 0.56, though I'm not sure if the reduction discussed in the paper is ratio preserving. Maybe a deeper look into the paper will help!

In the article "Approximate Max Cut" by S. Har-Peled, the last line of the paper mentioned that the real weighted version of max-cut has been discussed in

Approximating the cut-norm via grothendieck’s inequality, Noga Alon and Assaf Naor, SIAM Journal on Computing, 2006.

It is indeed an SDP algorithm, and it seems to me that the approximation ratio is 0.56, though I'm not sure if the reduction discussed in the paper is ratio preserving. Maybe a deeper look into the paper will help!

Source Link

In the article "Approximate Max Cut" by S. Har-Peled, the last line of the paper mentioned that the real weighted version of max-cut has been discussed in

Approximating the cut-norm via grothendieck’s inequality, Noga Alon and Assaf Naor, SIAM Journal on Computing, 2006.

It seems to me that the approximation ratio is 0.56, though I'm not sure if the reduction discussed in the paper is ratio preserving. Maybe a deeper look into the paper will help!