Timeline for Max-cut with negative weight edges
Current License: CC BY-SA 2.5
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 21, 2010 at 15:14 | comment | added | Warren Schudy | @Peter: your latest revision makes sense to me. Thanks for your patience! | |
| Oct 21, 2010 at 1:23 | history | edited | Peter Shor | CC BY-SA 2.5 |
making things a little clearer
|
| Oct 21, 2010 at 1:18 | comment | added | Peter Shor | @Warren, You choose $d$ large enough so that $c-dm<0$ for all cuts. This can be done by choosing $d$ sufficiently large. You then choose $a$ the right size so that the optimal cut is just barely above $0$. Read the last two paragraphs of my answer. | |
| Oct 20, 2010 at 23:02 | comment | added | Warren Schudy | @Peter: In the paragraph after the one I quoted you choose $a$ sufficiently small to make $f \approx -0.98 OPT$. You can't safely choose $a$ to be sufficiently large in one paragraph and sufficiently small in the next! In particular, there is no way to choose $a$ and $d$ to ensure that $c+a-(n-2)d>c-dm$ for all $0\le m \le n$ and simultaneously have $a-(n-2)d = f\approx -0.98 \cdot OPT$. This follows because $c+a-(n-2)d>c-dm$ for all $0\le m \le n$ implies that $f=a-(n-2)d > 0$. | |
| Oct 20, 2010 at 22:18 | comment | added | Peter Shor | You have to choose sufficiently large $a$ as well. | |
| Oct 20, 2010 at 21:48 | comment | added | Warren Schudy | I don't understand the following: "A cut with value c in G, where vertices u and v are on the same side of the cut, now has value at c−2dm where m is the number of vertices on the other side of the cut. A cut with (u,v) on opposite sides with original value c now has value c+a−(n−2)d. Thus, if we choose d large enough, we force the optimal cut in G∗ to have u and v on opposite sides." My issue is that choosing sufficiently large $d$ is insufficient to make $c+a-(n-2)d>c-dm$. In fact larger $d$ is counterproductive for making the optimal cut be one which separates $u$ and $v$. | |
| Oct 20, 2010 at 21:33 | history | edited | Peter Shor | CC BY-SA 2.5 |
fixed typo
|
| Oct 20, 2010 at 21:29 | comment | added | Peter Shor | I edited the solution to add those details. | |
| Oct 20, 2010 at 21:28 | history | edited | Peter Shor | CC BY-SA 2.5 |
Added details to algorithm
|
| Oct 20, 2010 at 20:31 | comment | added | Warren Schudy | @Peter: I also do not see how to choose a and d to make your proof work. | |
| Oct 20, 2010 at 20:22 | vote | accept | Aaron Roth | ||
| Oct 20, 2010 at 10:37 | history | edited | Peter Shor | CC BY-SA 2.5 |
fixed typo
|
| Oct 20, 2010 at 1:18 | comment | added | Aaron Roth | One issue is that if you add a negative edge between every pair of vertices, then you are modifying the value of different cuts by different amounts. (We subtract, say, $|S|\cdot|\bar{S}|\cdot a$ from the value of cut $S$). So we have the problem that the identity of the max-cut in the modified graph does not necessarily correspond to the max-cut in the original graph. | |
| Oct 20, 2010 at 1:11 | comment | added | Peter Shor | I agree, it doesn't quite work. But why can't you just add a negative edge between every pair of vertices, and repeat the same calculation? | |
| Oct 20, 2010 at 0:57 | comment | added | Aaron Roth | Hi Ian -- I don't think that works though. Why do there necessarily have to exist any $u$ and $v$ that are separated by the max-cut in the original graph, and remain separated by the max-cut after a heavy negative edge is added between them? Consider for example the complete graph -- adding a single, arbitrarily negative edge anywhere does not change the cut value at all. | |
| Oct 20, 2010 at 0:46 | comment | added | Ian | I believe $u$ and $v$ are arbitrary nodes separated by the max cut. You don't know what they are, but that doesn't matter because there are only $O(n^2)$ choices for $u$ and $v$, so you can run the algorithm for all possibilities and pick the largest cut found. | |
| Oct 19, 2010 at 22:58 | comment | added | Aaron Roth | Hi Peter -- I don't quite understand your answer. Could you elaborate? What are $u$ and $v$? If $u$ and $v$ are some pair of vertices separated by the max-cut on the original graph, how do you know that $u$ and $v$ continue to be separated by the max-cut on your modified graph? If we don't know this, how do we know that the max-cut on the modified graph has value $b-a$? | |
| Oct 19, 2010 at 22:45 | comment | added | Jukka Suomela | But what are your $u$ and $v$? The usual formulation of the max-cut problem does not have any "special nodes" that need to be separated. | |
| Oct 19, 2010 at 21:42 | history | answered | Peter Shor | CC BY-SA 2.5 |