Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms

作者：Punnen Abraham P^*; Sripratak Piyashat; Karapetyan Daniel

来源：Theoretical Computer Science, 2015, 565: 77-89.

DOI：10.1016/j.tcs.2014.11.008

• Quadratic programming
• Boolean variables
• Heuristics
• Worst-case analysis
• Domination analysis

We consider domination analysis of approximation algorithms for the bipartite boolean quadratic programming problem (BBQP) with m + n variables. A closed-form formula is developed to compute the average objective function value A of all solutions in O (mn) time. However, computing the median objective function value of the solutions is shown to be NP-hard. Also, we show that any solution with objective function value no worse than A dominates at least 2(m+n-2) solutions and this bound is the best possible. Further, we show that such a solution can be identified in O (mn) time and hence the domination ratio of this algorithm is at least 1/4. We then show that for any fixed natural numbers a and b such that eta = a/b > 1, no polynomial time approximation algorithm exists for BBQP with domination ratio larger than 1 - 2(1-eta)/eta(m+n), unless P = NP. It is shown that some powerful local search algorithms can get trapped at a local maximum with objective function value less than A. One of our approximation algorithms has an interesting rounding property which provides a data dependent lower bound on the optimal objective function value. A new integer programming formulation of BBQP is also given and computational results with our rounding algorithms are reported.

• 出版日期2015-2-2