# 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.
##### MSC:
 90C09 Boolean programming 65K05 Numerical mathematical programming methods