On the convergence rate of swap-collide algorithm for simple task assignment

This paper provides a convergence rate analysis of the swap-collide algorithm for simple assignment problems. Swap-collide is a distributed algorithm that assigns a unique task to each agent assuming that the cost of each assignment is identical and has applications in resource-constrained multiagent systems; prior work has shown that this assignment procedure converges in finite-time. In this paper, we provide an analytical framework to establish the convergence rate of swap-collide, and show that for a network of size N, the lower and upper bounds for the convergence rate are O(N³).