A solvable case of quadratic 0-1 programming (Q1079494): Difference between revisions

The problem of minimizing a quadratic function \(f(x)=x^ tQx+cx\) with symmetric matrix Q and Boolean x is considered. Finding the minimum of f(x) is equivalent to finding an assignment of values to the variables \(s_ i\) \((s_ i=2x_ i-1\), \(s_ i\in \{-1,1\})\) that maximizes \(\sum \{w_{ij}:\) \(s_ i=-s_ i\}\) where \(w_{ij}=(1/4)q_{ij}\) for \(1\leq i\leq j\leq n\) and \(w_{0j}=c_ j+\sum^{n}_{i=j}q_{ji}\) for \(0\leq j\leq n\). This is equivalent to finding a maximum weighted cut in the graph \(H=(U,F)\), where \(U=\{0,1,...,n\}\), and \(ij\in F\Leftrightarrow w_{ij}\neq 0\). The case when the graph \(H=(U,F)\) has a vertex u such that \(H\setminus u\) is series-parallel is considered. In this case an algorithm having computing time 0(n) is proposed.