Interactive Optimization of Submodular Functions under Matroid Constraints
Abstract
Various practical optimization problems can be formalized as the search of an optimal independent set in a matroid. When the set function to be optimized is additive, this problem can be exactly solved using a greedy algorithm. However, in some situations, the set function is not exactly known and must be elicited before or during the optimization process. Moreover, the set function is not always additive due to possible interactions between the elements of the set. Here we consider the problem of maximizing a submodular set function under a matroid constraint. We propose two interactive approaches aiming at interweaving the elicitation of the submodular set function with the construction of an optimal independent subset subject to a matroid constraint. The first one is based on a greedy algorithm and the other is based on local search. These algorithms are tested on practical problems involving a matroid structure and a submodular function to be maximized.
Origin | Files produced by the author(s) |
---|