Valuated matroid-based algorithm for submodular welfare problem

Valuated matroid-based algorithm for submodular welfare problem

0.00 Avg rating0 Votes
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: ,
Keywords: combinatorial optimization, programming: convex, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.