Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem

arXiv1210.3684MaRDI QIDQ6236330FDOQ6236330

Authors: Daniel Karapetyan, Abraham P. Punnen 

Publication date: 13 October 2012

Abstract: We study the Bipartite Unconstrained 0-1 Quadratic Programming Problem (BQP) which is a relaxation of the Unconstrained 0-1 Quadratic Programming Problem (QP). Applications of the BQP include mining discrete patterns from binary data, approximating matrices by rank-one binary matrices, computing cut-norm of a matrix, and solving optimization problems such as maximum weight biclique, bipartite maximum weight cut, maximum weight induced subgraph of a bipartite graph, etc. We propose several classes of heuristic approaches to solve the BQP and discuss a number of construction algorithms, local search algorithms and their combinations. Results of extensive computational experiments are reported to establish the practical performance of our algorithms. For this purpose, we propose several sets of test instances based on various applications of the BQP. Our algorithms are compared with state-of-the-art heuristics for QP which can also be used to solve BQP with reformulation. We also study theoretical properties of the neighborhoods and algorithms. In particular, we establish complexity of all neighborhood search algorithms and establish tight worst-case performance ratio for the greedy algorithm.

This page was built for publication: Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6236330)