Talk:Maximum cut

Rename to Maximum cut?[edit]

Is there any reason why this page is called Maximal cut and not Maximum cut? Cf., e.g., Cut (graph theory) and [1]. After renaming, we could also change the redirects Max cut and Maxcut to point here, instead of Cut (graph theory). – Miym (talk) 23:29, 21 December 2008 (UTC)[reply]

I agree. Fortunately, someone has done it. Zaslav (talk) 02:20, 26 August 2009 (UTC)[reply]

State the problem[edit]

We need a clean definition of the two main problems treated here: Max cut and max weighted cut. Zaslav (talk) 02:02, 26 August 2009 (UTC)[reply]

Done. Zaslav (talk) 02:32, 26 August 2009 (UTC)[reply]

Practical uses?[edit]

So, the article is all nice and full of interesting theory, but what about the applications of the maximum cut problem? Where is it used in practice and how exactly is it used in those areas? The lack of answers to these questions is of course not only a problem of just this article but a general problem in university level text books and courses, but anyway. —ZeroOne (talk / @) 14:57, 10 October 2009 (UTC)[reply]

Here is a paper that mentions two applications:

Barahona, Francisco; Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1988), "An application of combinatorial optimization to statistical physics and circuit layout design", Operations Research, 36 (3): 493–513, doi:10.1287/opre.36.3.493, JSTOR 170992

Max-cut is also closely related to MAX-2-SAT, but this might not count as a practical use... — Miym (talk) 15:46, 10 October 2009 (UTC)[reply]