Fast Optimization of Boolean Quadratic Functions via Iterative Submodular Approximation and Max-flow

摘要

We consider the NP-hard combinatorial optimization problem of minimizing arbitrary quadratic forms over the {0, 1 } (Boolean) lattice. While polynomial-time approximation algorithms do exist for such problems, they suffer from the practical drawback of being computationally involved - often a side effect of being agnostic to the combinatorial structure inherent in the problem. In this paper, we propose a computationally lightweight approximation alternative which specifically exploits the combinatorial structure of the problem. The key result underlying our approach is that any Boolean quadratic function can be expressed as a difference of quadratic sub-modular functions, which enables us to construct and iteratively minimize a sequence of global submodular upper bounds on the cost function. This entails solving a quadratic submodular function minimization problem at each step, which can be efficiently accomplished via the seminal Max-Flow algorithm. Overall, our algorithm performs iterative approximation by solving a sequence of maximum-flow problems. The merits of using this approach are illustrated via simulations which indicate the very favorable performance of our algorithm.