The Ajtai–Komlós–Tusnády theorem (also known as the AKT optimal matching theorem) is a result in probabilistic combinatorics. Given two random, distinct sets of points formula_1 and formula_2 in the unit square formula_3, the theorem gives then upper and lower bounds for the minimal total distance needed to match the points in one set to those in the other.
The theorem was proven in 1984 by the Hungarian mathematicians Miklós Ajtai, János Komlós, and Gábor Tusnády.
Statement.
Let formula_4 and formula_5 be two independent random vectors, uniformly distributed over formula_3 (i.e., formula_7). Let formula_8 denote the symmetric group, and formula_9 the Euclidean norm on formula_10.
Then,
formula_11
where formula_12 are real constants.
formula_14     see Landau notation.
formula_15
with high probability.