Quadratic pseudo-Boolean optimization: Difference between revisions

Revision as of 17:16, 14 January 2019

Revision as of 17:38, 14 January 2019

Line 13:

:<math> w_{pq}(0, 0) + w_{pq}(1, 1) \le w_{pq}(0, 1) + w_{pq}(1, 0) </math>

then the function can be efficiently optimised with [[graph cut optimization]]. It is indeed possible to represent isit with a non-negative weighted [[graph (discrete mathematics)|graph]], and the global minimum can be found in polynomial time by computing a [[minimum cut]] of the graph, which can be computed with algorithms such as [[Ford–Fulkerson algorithm|Ford–Fulkerson]], [[Edmonds–Karp algorithm|Edmonds–Karp]], and [[Boykov–Kolmogorov algorithm|Boykov–Kolmogorov]]'s.

If the function is not submodular, then the problem is [[NP-hard]] in the general case and it is not always possible to solve it exactly in polynomial time. It is possible to replace the target function with a similar but submodular approximation, e.g. by removing all non-submodular terms or replacing them with submodular approximations, but such approach is generally sub-optimal and it produces satisfying results only if the number of non-submodular terms is relatively small. <ref name="review" />