zbMATH — the first resource for mathematics

On the minimization of quadratic polynomials of Boolean functions. (Russian) Zbl 0572.90072
The paper deals with the following NP-hard minimization problem \[ (P)\quad \min_{x\in B^ n}\sum^{m}_{i=1}a_ i(1-x_ i)+\sum_{j<k}b_{jk}x_ jx_ k \] where \(a_ i\), \(b_{jk}\geq 0\), \(i=1,...,m\), \(1\leq j<k\leq m\). This problem is equivalent to the set covering problem \[ (CP)\quad \min \sum^{m}_{i=1}a_ iu_ i+\sum_{j<k}b_{jk}v_{jk} \] subject to \(u_ j+u_ k+v_{jk}\geq 1\), \(1\leq j<k\leq m\), \(u_ i,v_{jk}\in \{0,1\}\), \(i=1,...,m\), \(1\leq j<k\leq m\). Denote by LCP the linear relaxation of CP. The main results of the paper are: (i) There exists an optimal solution \((\tilde u^*_ i)\), \((\tilde v^*_{jk})\) of LCP such that \(\tilde u^*_ i,\tilde v^*_{jk}\in \{0,,1\}\), \(i=1,...,m\), \(1\leq j<k\leq m\). (ii) If we define \(I_{\ell}=\{i| \tilde u^*_ i=\ell \}\), \(\ell \in \{0,1\}\), then there exists an optimal solution \((u^*_ i)\), \((v^*_{jk})\) of CP such that \(u^*_ i=\ell\) for \(i\in I_{\ell}\) and \(\ell \in \{0,1\}\). (iii) An \(O(m^ 3)\) algorithm for LCP.
Based on these results exact and \(O(m^ 3)\) approximation algorithms with a performance guarantee are constructed for problem P.
90C09 Boolean programming
65K05 Numerical mathematical programming methods