The maximum weight matching (MWM) for bipartite graphs is a fundamental combinatorial optimization problem that can be found extensively in many engineering applications such as job assignment and resource allocation. The traditional solution to MWM requires all weights to be collected on a centralized entity. In this paper, we present a multi-agent approach to solving MWM by message passing among all involved agents in a concurrent way. The proposed distributed algorithm is motivated by two related factors: first, in certain circumstances no server is available to provide centralized services, and second, the agents may not be willing to share the secret weight information to others. In the proposed approach, a MWM problem is first converted to the prime-dual linear programming setting, and a nonlinear dynamics is introduced to evolve to the solution. Each agent updates its estimates of the prime-dual variables following the dynamics, using a step parameter determined only by the size of the problem, before sending messages to other agents. In this paper, we prove the optimality, convergence of the proposed algorithm and study the experimental results by simulating some typical problem setups. The simulation experiments demonstrate the effectiveness of the proposed approach.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com