Distributed balanced color assignment on arbitrary networks (Q2290638)

A generalized bipartite matching problem is studied, the balanced color assignment problem: a set of \(n\) agents hold items of \(m\) possible colors and they are connected by an asynchronous arbitrary communication network and have to distributively find a repartition of the colors such that the amount of colors for each agent is as balanced as possible. In particular, a lower bound is proposed on the message complexity of the balanced color assignment problem that holds even for approximate solutions. The authors propose a novel polynomial-time distributed algorithm designed to run on an arbitrary network with the agents as nodes. The efficiency in terms of time and complexity is proved for large diameter graphs.