EcoSta 2017: Start Registration
View Submission - EcoSta2017
A0554
Title: Binary quadratic program algorithms for large scale problems Authors:  Benson Shu Yan Lam - Hang Seng Management College (China) [presenting]
Abstract: Many image processing, pattern recognition, and computer vision problems can be formulated as binary quadratic programming (BQP) problems. Due to the NP-hard nature of these problems, the calculation of an extremely large BQP problem with a very good quality solution in real time is still a challenging and unsolved problem for which many different methods have been developed. For a typical image processing problem, it can involve an image with size $600x700$. Then, the corresponding BQP problem needs to deal with at least an $nxn$ matrix with $n=600x700$. In the current stage of development, spectral and semidefinite relaxation techniques are widely used to solve image processing, pattern recognition, and computer vision problems. The spectral approach is simple and fast, but its error bounds are loose with low solution qualities. The semidefinite approach has tighter error bounds with high solution qualities, but its computational complexity is high. We first show how real-world large-scale problems be formulated as BQP problems with complicated linear and/or quadratic constraints. Then, we present algorithms that can find good solutions in real time.