On the convergence rate of swap-collide algorithm for simple task assignment
Sam Safavi, Usman A. Khan · 2014 48th Asilomar Conference on Signals, Systems and Computers · 2014
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(N3).