cot.assignment

cot.assignment(W, C, eps, seed=0)

This function sloves an additive approximation of the assignment problem between two discrete distributions and returns assignment plan and cost. This function is a numpy implementation version of the parallelizable combinatorial algorithm [2] for assignment problem.

Parameters:

• W (numpy array, shape (n, n)) – A n by n cost matrix, each W(i,j) represents the cost between i-th type b and j-th type vertex from the samples of supply and demand distribution.

• C (float) – The scale of cost metric.

• eps (float) – The additive error of optimal transport distance, the value of \(\epsilon\) in paper [2].

Returns:

• Mb (numpy array, shape (n,)) – A 1 by n array, each i represents the index of type a vertex (j-th column in cost matrix, i.e. W[:,j]) that is assigned with ith type b vertex.

• yA (numpy array, shape (n,)) – A 1 by n array, each i represents the final dual value of ith type a vertex.

• yB (numpy array, shape (n,)) – A 1 by n array, each i represents the final dual value of ith type b vertex.

• total_cost (float) – Total cost of the final assignment.

References

[2] (1,2)

Lahn, Nathaniel, Sharath Raghvendra, and Kaiyi Zhang. A combinatorial algori-thm for approximating the optimal transport in the parallel and mpc settings. Advances in Neural Information Processing Systems (NeurIPS) 36, 2023