Consensus Approaches to the Assignment Problem

The assignment problem, also regarded as the bipartite Maximum Weighted Matching problem, is a fundamental problem in combinatorial optimization and provides several applications, especially in the areas of multi-agent coordination, distributed computing and distributed manufacturing. In particular, it has been shown that optimal task and resource allocation can be reduced to an instance of the assignment problem.

This work aims at designing a consensus protocol to solve the assignment problem in a completely distributed manner without any central management or global knowledge. The main application of this work is sensor dispatch, an emerging problem in wireless sensor networks where a subset of mobile sensors need to decide how to move in order to optimize certain global objectives while maintaining the coverage ability.