The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases

© 2015 Elsevier B.V. All rights reserved. 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 har...

Full description

Saved in:
Bibliographic Details
Main Authors: Abraham P. Punnen, Piyashat Sripratak, Daniel Karapetyan
Format: Journal
Published: 2018
Subjects:
Online Access:https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84938291413&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/44164
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Chiang Mai University
id th-cmuir.6653943832-44164
record_format dspace
spelling th-cmuir.6653943832-441642018-04-25T07:46:22Z The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases Abraham P. Punnen Piyashat Sripratak Daniel Karapetyan Agricultural and Biological Sciences © 2015 Elsevier B.V. All rights reserved. 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. 2018-01-24T04:38:50Z 2018-01-24T04:38:50Z 2015-10-01 Journal 0166218X 2-s2.0-84938291413 10.1016/j.dam.2015.04.004 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84938291413&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/44164
institution Chiang Mai University
building Chiang Mai University Library
country Thailand
collection CMU Intellectual Repository
topic Agricultural and Biological Sciences
spellingShingle Agricultural and Biological Sciences
Abraham P. Punnen
Piyashat Sripratak
Daniel Karapetyan
The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases
description © 2015 Elsevier B.V. All rights reserved. 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.
format Journal
author Abraham P. Punnen
Piyashat Sripratak
Daniel Karapetyan
author_facet Abraham P. Punnen
Piyashat Sripratak
Daniel Karapetyan
author_sort Abraham P. Punnen
title The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases
title_short The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases
title_full The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases
title_fullStr The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases
title_full_unstemmed The bipartite unconstrained 0-1 quadratic programming problem: Polynomially solvable cases
title_sort bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
publishDate 2018
url https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84938291413&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/44164
_version_ 1681422508720390144