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

2012/12/15 by Punnen, Abraham P., Sripratak, Piyashat, Karapetyan, Daniel
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1212.3736

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=(q_ij) is fixed, then BQP01 can be solved in polynomial time. When Q is of rank one, we provide an O(nlog n) algorithm and this complexity reduces to O(n) with additional assumptions. Further, if q_ij=a_i+b_j for some a_i and b_j, then BQP01 is shown to be solvable in O(mnlog n) time. By restricting m=O(log n), we obtain yet another polynomially solvable case of BQP01 but the problem remains MAX SNP hard if m=O(√[k]n) 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(log n) then we show that BQP01 polynomially solvable but it is NP-hard if this number is O(√[k]n) for any fixed k. Keywords: quadratic programming, 0-1 variables, polynomial algorithms, complexity, pseudo-Boolean programming.

Related

• Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem
• A Polynomial-Time Algorithm for Unconstrained Binary Quadratic\n Optimization
• Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation
• Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables
• Complexity Aspects of Fundamental Questions in Polynomial Optimization