Quadratic pseudo-Boolean optimization: Difference between revisions

Content deleted Content added
Changed couple to pair as this seemed to be the intended meaning here.
Line 67:
== 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 ''noramlnormal form'', which is always defined 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>.