Cyclical monotonicity is the combinatorial fingerprint of optimality:
a coupling is optimal exactly when no finite cycle of reassignments
lowers the cost. Checking every permutation is factorial, so the test
here is over all transpositions, the two-cycle case.
Arguments
- X, Y
Point sets, kept for interface symmetry.
- Cost
Cost matrix with Cost[i, j] = c(x_i, y_j).
- perm
Zero-based assignment: y_i matched to x_perm[i].
Value
List with is_cm, slack, estimate, n.
Details
Formula: for all (i, j),
c(x_s(i), y_i) + c(x_s(j), y_j) <= c(x_s(j), y_i) + c(x_s(i), y_j).
References
Villani, C. (2003). AMS GSM 58, theorem 2.12.
Examples
X <- c(0, 1); Y <- c(0, 1)
Cost <- outer(X, Y, function(a, b) (a - b)^2)
Otcw(X, Y, Cost, perm = c(1L, 0L))$is_cm # crossed matching: improvable
#> [1] 0
Otcw(X, Y, Cost, perm = c(0L, 1L))$is_cm # identity: cyclically monotone
#> [1] 1
