Post by Viktor Henriksson on Aug 26, 2020 19:39:23 GMT
Hi all!
I have a question regarding the last lecture that I can't really seem to wrap my head around, so I thought I should try posting here, to see if somebody else knows the answer (or have the same problem, and want to discuss it).
As I understand it, we are trying to show that it is hard to approximate Max Cut better than the GW-algorithm. Comparing to how we've usually done I would have thought that we, morally speaking, would want to show that if we are able to solve Max Cut better, we get a solution to the corresponding unique game that contradicts the UGC.
This is where I get lost. On page 4 of L-8 we construct a graph from a unique game, and we do some tricks to make it difficult to figure out the max cut. Thus my thought would have been that we we're to use our (too good) max cut algorithm on that graph. However, I can not how figuring out an approximation of a max cut there would help us in obtaining an approximation for the UG-instance. It seems likely that I am missing something rather fundamental. Would anyone like to enlighten me? 😅
All the best,
Viktor
I have a question regarding the last lecture that I can't really seem to wrap my head around, so I thought I should try posting here, to see if somebody else knows the answer (or have the same problem, and want to discuss it).
As I understand it, we are trying to show that it is hard to approximate Max Cut better than the GW-algorithm. Comparing to how we've usually done I would have thought that we, morally speaking, would want to show that if we are able to solve Max Cut better, we get a solution to the corresponding unique game that contradicts the UGC.
This is where I get lost. On page 4 of L-8 we construct a graph from a unique game, and we do some tricks to make it difficult to figure out the max cut. Thus my thought would have been that we we're to use our (too good) max cut algorithm on that graph. However, I can not how figuring out an approximation of a max cut there would help us in obtaining an approximation for the UG-instance. It seems likely that I am missing something rather fundamental. Would anyone like to enlighten me? 😅
All the best,
Viktor