mlsanityData to 7 Oct 2026

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

arXiv 1403.7721 ↗First posted 30 Mar 2014cs.CC cs.DScited by 13

Not on the map. Why?

Abstract (arXiv)

We show that for every positive ε > 0, unless NP subset BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2^log1-ε 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 - ε vs ε hard assuming the Unique Games Conjecture. Then, we present an O(√n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Mar 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 3; 2023: 0; 2024: 4; 2025: 3; 2026: 1.

13 papers.

Sort:

  1. 2022Git Re-Basin: Merging Models modulo Permutation Symmetriescited by 460
  2. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
  3. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  4. 2021Correlation detection in trees for planted graph alignmentcited by 14
  5. 2022Seeded graph matching for the correlated Gaussian Wigner model via the projected power methodcited by 4
  6. 2024Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problemcited by 3
  7. 2024The graph alignment problem: fundamental limits and efficient algorithmscited by 2
  8. 2025Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguitycited by 2
  9. 2025Graph Alignment via Birkhoff Relaxationcited by 2
  10. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  11. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0
  12. 2025Statistical-computational gap in multiple Gaussian graph alignmentcited by 0
1 more
  1. 2026Phase Transition in Convex Relaxations for Graph Alignmentcited by 0