Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm

DOI10.1007/978-3-642-14165-2_50zbMATH Open1288.68273arXiv1403.7721OpenAlexW2569881749MaRDI QIDQ3587410FDOQ3587410

Authors: Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko 

Publication date: 7 September 2010

Published in: ACM Transactions on Algorithms, Automata, Languages and Programming (Search for Journal in Brave)

Abstract: We show that for every positive $epsilon>0$, unless NP $subset$ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than $2^{lo{g}^{1-epsilon}n}$ by a reduction from the maximum label cover problem. Our result also implies that Approximate Graph Isomorphism is not robust and is in fact, $1-epsilon$ vs $epsilon$ hard assuming the Unique Games Conjecture. Then, we present an $O(sqrtn)$-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.

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

Recommendations

• Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm
• On the maximum quadratic assignment problem
• On the maximum quadratic assignment problem
• Maximizing Polynomials Subject to Assignment Constraints
• Maximizing polynomials subject to assignment constraints

zbMATH Keywords

quadratic assignment probleminapproximability

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Cited In (16)

• A unified FFT-based approach to maximum assignment problems related to transitive finite group actions
• Testing correlation of unlabeled random graphs
• On the maximum edge-pair embedding bipartite matching
• Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm
• On the maximum quadratic assignment problem
• Spectral alignment of correlated Gaussian matrices
• Correlation detection in trees for planted graph alignment
• Efficient random graph matching via degree profiles
• Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
• Maximizing polynomials subject to assignment constraints
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• Maximizing Polynomials Subject to Assignment Constraints
• On the maximum quadratic assignment problem
• Graph similarity and approximate isomorphism
• Minimum congestion mapping in a cloud

This page was built for publication: Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm

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