Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm

DOI10.1007/978-3-642-14165-2_50zbMath1288.68273arXiv1403.7721OpenAlexW2569881749MaRDI QIDQ3587410

M. I. Sviridenko, Rajsekar Manokaran, Konstantin Makarychev

Publication date: 7 September 2010

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

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

zbMATH Keywords

quadratic assignment probleminapproximability

Mathematics Subject Classification ID

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

Related Items (10)

A unified FFT-based approach to maximum assignment problems related to transitive finite group actions ⋮ Spectral alignment of correlated Gaussian matrices ⋮ 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 ⋮ Testing correlation of unlabeled random graphs ⋮ Graph Similarity and Approximate Isomorphism ⋮ Maximizing Polynomials Subject to Assignment Constraints ⋮ On the maximum edge-pair embedding bipartite matching ⋮ 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