2013/03/01 by Abraham P. Punnen, Piyashat Sripratak, Daniel Karapetyan
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Algorithm #Approximation algorithm #Bipartite graph #Boolean function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Function (biology) #Integer (computer science) #Mathematics #Optimization and Search Problems #Rounding #Time complexity #Upper and lower bounds #Value (mathematics) #cs.DM #math.CO #math.OC
paper · pdf · doi:10.1016/j.tcs.2014.11.008
published as Theoretical Computer Science 565 (2015), 77-89 · 20 pages
arxiv created 2013/03/01 · openalex publication_date 2014/11/16 · arxiv updated 2014/12/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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 2m+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 dominance ratio of this algorithm is at least 1/4. We then show that for any fixed rational number a > 1, no polynomial time approximation algorithm exists for BBQP with dominance ratio larger than 1-2(m+n)(1-a)/a, unless P=NP. We then analyze some powerful local search algorithms and show that they 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.