Quadratic pseudo-Boolean optimization: Difference between revisions

Revision as of 12:42, 18 December 2019

Revision as of 21:22, 9 October 2020

Line 69:

== Notes ==

<references group="note">

<ref name="normal form">The representation of a pseudo-Boolean function with coefficients <math>\mathbf{w} = (w_0, w_1, \dots, w_{nn})</math> is not unique, and if two coefficient vectors <math>\mathbf{w}</math> and <math>\mathbf{w}'</math> represent the same function then <math>\mathbf{w}'</math> is said to be a reparametrisation of <math>\mathbf{w}</math> and vice versa. In some constructions it is useful to ensure that the function has a specific form, called ''noraml form'', which is always defindeddefined for any function, and it is not unique. A function <math>f</math> is in normal form if the two following conditions hold (Kolmogorov and Rother (2007)):

# <math>\min \{ w_p^0, w_p^1 \} = 0</math> for each <math>p \in V</math>;

# <math>\min \{ w_{pq}^{0j}, w_{pq}^{1j} \} = 0</math> for each <math>(p, q) \in E</math> and for each <math>j \in \{0, 1\}</math>.