An α-approximation Protocol for the Generalized Mutual Assignment Problem

This paper presents a new distributed solution protocol, called DisLRPα, for the Generalized Mutual Assignment Problem (GMAP). The GMAP is a typical distributed combinatorial optimization problem whose goal is to maximize social welfare of the agents. Unlike the previous protocol for the GMAP, DisLRPα can provide a theoretical guarantee on global solution quality. In DisLRPα, as with in the previous protocol, the agents repeatedly solve their local problems while coordinating their local solutions using a distributed constraint satisfaction technique. The key difference is that, in DisLRPα, each agent is required to produce a feasible solution whose local objective value is not lower than α (0 < α ≤ 1) times the local optimal value. Our experimental results on benchmark problem instances show that DisLRPα can certainly find a solution whose global objective value is higher than that theoretically guaranteed. Furthermore, they also show that, while spending extra communication and computation costs, DisLRPα can produce a significantly better solution than the previous protocol if we set α appropriately.

Authors

• Katsutoshi Hirayama Kobe University

Keywords

No keywords are indexed for this paper.