Skip to content

Algorithms for solving the quadratic assignment problem (QAP) implemented in Julia.

License

Notifications You must be signed in to change notification settings

flixpar/QuadraticAssignmentProblem.jl

Repository files navigation

Quadratic Assignment Problem

Algorithms for (approximately) solving the quadratic assignment problem (QAP) implemented in Julia.

Exact algorithms:

  • Quadratic integer programming
  • Linearization

Approximation algorithms:

  • "On the Maximum Quadratic Assignment Problem" by Nagarajan and Sviridenko (NS)
  • "Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm" by Makarychev, Manokaran, and Sviridenko (MMS)

Heuristic algorithms:

  • Fast Approximate QAP
  • Random search
  • LP + LAP rounding