Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
From MaRDI portal
Publication:482289
DOI10.1016/j.tcs.2014.11.008zbMath1315.90027arXiv1303.0160MaRDI QIDQ482289
Daniel Karapetyan, Piyashat Sripratak, Abraham P. Punnen
Publication date: 22 December 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1303.0160
90C20: Quadratic programming
90C59: Approximation methods and heuristics in mathematical programming
90C09: Boolean programming
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
The Bipartite QUBO, Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking, The bipartite quadratic assignment problem and extensions, 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, Markov chain methods for the bipartite Boolean quadratic programming problem, The generalized vertex cover problem and some variations, 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, The bipartite Boolean quadric polytope, Analysis of 2-Opt Heuristic for the Winner Determination Problem Under the Chamberlin-Courant System, Unnamed Item, Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
- A survey of very large-scale neighborhood search techniques
- Domination analysis for minimum multiprocessor scheduling
- Dominance guarantees for above-average solutions
- Local search and the local structure of NP-complete problems
- Minimum perfect bipartite matchings and spanning trees under categorization
- Differential approximation algorithms for some combinatorial optimization problems
- 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
- A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
- Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
- Domination analysis of some heuristics for the traveling salesman problem
- On \(k\)-sum optimization
- Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
- Path relinking for unconstrained binary quadratic programming
- The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
- Minimum number of below average triangles in a weighted complete graph
- Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
- z-Approximations
- Adaptive Memory Tabu Search for Binary Quadratic Programs
- Domination Analysis of Algorithms for Bipartite Boolean Quadratic Programs
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Low-Rank Matrix Approximation with Weights or Missing Data Is NP-Hard
- Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
- Inapproximability of Maximum Weighted Edge Biclique and Its Applications
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
- Algorithms with large domination ratio
- Combinatorial dominance guarantees for problems with infeasible solutions
- Approximating the Cut-Norm via Grothendieck's Inequality
- TSP tour domination and Hamilton cycle decompositions of regular digraphs
