A Multi-agent Approach to the Maximum Weight Matching Problem
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.
multi-agent neural networks message passing
Gang SHEN Yun ZHANG
School of Software Engineering, Huazhong University of Science and Technology Wuhan, China 430074
国际会议
The 21st ISPE International Conference on Concurrent Engineering (2014国际并行工程学术会议)
北京
英文
162-171
2014-09-08（万方平台首次上网日期，不代表论文的发表时间）