Graph cut optimization: Difference between revisions

Revision as of 12:09, 6 July 2019

Revision as of 19:50, 7 July 2019

Line 1:

{{short description|Combinatorial optimization method for a family of functions of discrete variables}}

'''Graph cut optimization''' is a [[combinatorial optimization]] method applicable to a family of [[function (mathematics)|function]]s of [[Continuous or discrete variable|discrete variable]]s, named after the concept of [[cut (graph theory)|cut]] in the theory of [[flow network]]s. Thanks to the [[max-flow min-cut theorem]], determining the [[minimum cut]] over a [[graph (discrete mathematics)|graph]] representing a flow network is equivalent to computing the [[maximum flow]] over the network. Given a [[pseudo-Boolean function]] <math>f</math>, if it is possible to construct a flow network with positive weights such that

* each cut <math>C</math> of the network can be mapped to an an assignment of variables <math>\mathbf{x}</math> to <math>f</math> (and vice versa), and

* the flow through <math>C</math> equals <math>f(\mathbf{x})</math> (up to an additive constant)

then it is possible to find the [[global optimum]] of <math>f</math> in [[polynomial time]] by computing a minimum cut of the graph. The mapping between cuts and variable assignments is done by representing each variable with one node in the graph and, given a cut, each variable will have a value of 0 if the corresponding node belongs to the component connected to the source, or 1 if it belong to the component connected to the sink.