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

Aritra Konar, Nicholas D. SidiropoulosICASSP 2019 · OpenReview

Abstract

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.
BibTeX
@inproceedings{konar2019fast,
  author = {Aritra Konar and Nicholas D. Sidiropoulos},
  title = {{Fast Optimization of Boolean Quadratic Functions via Iterative Submodular Approximation and Max-flow}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=Bmufr-V8LzD},
}

Loading related content...

Figure