Punnen, Abraham P and Sripratak, Piyashat and Karapetyan, Daniel (2015) The bipartite unconstrained 0–1 quadratic programming problem: Polynomially solvable cases. Discrete Applied Mathematics, 193. pp. 1-10. DOI https://doi.org/10.1016/j.dam.2015.04.004
Punnen, Abraham P and Sripratak, Piyashat and Karapetyan, Daniel (2015) The bipartite unconstrained 0–1 quadratic programming problem: Polynomially solvable cases. Discrete Applied Mathematics, 193. pp. 1-10. DOI https://doi.org/10.1016/j.dam.2015.04.004
Punnen, Abraham P and Sripratak, Piyashat and Karapetyan, Daniel (2015) The bipartite unconstrained 0–1 quadratic programming problem: Polynomially solvable cases. Discrete Applied Mathematics, 193. pp. 1-10. DOI https://doi.org/10.1016/j.dam.2015.04.004
Abstract
We consider the bipartite unconstrained 0-1 quadratic programming problem (BQP01) which is a generalization of the well studied unconstrained 0-1 quadratic programming problem (QP01). BQP01 has numerous applications and the problem is known to be MAX SNP hard. We show that if the rank of an associated m×n cost matrix Q=(qij) is fixed, then BQP01 can be solved in polynomial time. When Q is of rank one, we provide an O(nlogn) algorithm and this complexity reduces to O(n) with additional assumptions. Further, if qij=ai+bj for some ai and bj, then BQP01 is shown to be solvable in O(mnlogn) time. By restricting m=O(logn), we obtain yet another polynomially solvable case of BQP01 but the problem remains MAX SNP hard if m=O(nk) for a fixed k. Finally, if the minimum number of rows and columns to be deleted from Q to make the remaining matrix non-negative is O(logn), then we show that BQP01 is polynomially solvable but it is NP-hard if this number is O(nk) for any fixed k.
Item Type: | Article |
---|---|
Additional Information: | 20 pages |
Uncontrolled Keywords: | Quadratic programming 0–1 variables Polynomial algorithms Complexity Pseudo-Boolean programming |
Subjects: | Q Science > QA Mathematics |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 24 May 2018 10:26 |
Last Modified: | 07 Aug 2024 20:09 |
URI: | http://repository.essex.ac.uk/id/eprint/22056 |
Available files
Filename: 1212.3736v3.pdf