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

DOI10.1016/J.TCS.2014.11.008zbMATH Open1315.90027arXiv1303.0160OpenAlexW2078140591MaRDI QIDQ482289FDOQ482289

Authors: Abraham P. Punnen, Piyashat Sripratak, Daniel Karapetyan 

Publication date: 22 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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 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.

Full work available at URL: https://arxiv.org/abs/1303.0160

Recommendations

• Domination analysis of algorithms for bipartite Boolean quadratic programs
• Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
• Markov chain methods for the bipartite Boolean quadratic programming problem
• The bipartite Boolean quadric polytope
• Algorithms with large domination ratio

zbMATH Keywords

heuristicsquadratic programmingworst-case analysisBoolean variablesdomination analysis

Mathematics Subject Classification ID

Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Boolean programming (90C09)

Cites Work

• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximating the Cut-Norm via Grothendieck's Inequality
• Differential approximation algorithms for some combinatorial optimization problems
• Path relinking for unconstrained binary quadratic programming
• \(z\)-approximations
• A survey of very large-scale neighborhood search techniques
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
• Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
• Adaptive memory tabu search for binary quadratic programs
• Domination Analysis of Algorithms for Bipartite Boolean Quadratic Programs
• Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Low-Rank Matrix Approximation with Weights or Missing Data Is NP-Hard
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Local search and the local structure of NP-complete problems
• Domination analysis of some heuristics for the traveling salesman problem
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• On \(k\)-sum optimization
• Minimum perfect bipartite matchings and spanning trees under categorization
• On the quality of local search for the quadratic assignment problem
• Domination analysis of combinatorial optimization problems.
• Domination analysis of greedy heuristics for the frequency assignment problem.
• TSP heuristics: domination analysis and complexity
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Minimum number of below average triangles in a weighted complete graph
• Inapproximability of Maximum Weighted Edge Biclique and Its Applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms with large domination ratio
• Combinatorial dominance guarantees for problems with infeasible solutions
• Title not available (Why is that?)
• TSP tour domination and Hamilton cycle decompositions of regular digraphs
• Domination analysis for minimum multiprocessor scheduling
• Dominance guarantees for above-average solutions

Cited In (14)

• Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking
• Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
• The bipartite Boolean quadric polytope
• Title not available (Why is that?)
• Markov chain methods for the bipartite Boolean quadratic programming problem
• The generalized vertex cover problem and some variations
• Title not available (Why is that?)
• The bipartite quadratic assignment problem and extensions
• Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System
• The bilinear assignment problem: complexity and polynomially solvable special cases
• Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
• Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms
• The Bipartite QUBO
• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

This page was built for publication: Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482289)