Article ID: | iaor201526034 |
Volume: | 229 |
Issue: | 1 |
Start Page Number: | 565 |
End Page Number: | 590 |
Publication Date: | Jun 2015 |
Journal: | Annals of Operations Research |
Authors: | Murota Kazuo, Maehara Takanori |
Keywords: | combinatorial optimization, programming: convex, heuristics |
An algorithm for the submodular welfare problem is proposed based on the theory of discrete convex analysis. The proposed algorithm is a heuristic method built upon the valuated matroid partition algorithms, and gives the exact optimal solution for a reasonable subclass of submodular welfare problems. The algorithm has a guaranteed approximation ratio for a special case. Computational results show fairly good performance of the proposed algorithm.