Interactive Optimization of Submodular Functions under Matroid Constraints - Sorbonne Université Access content directly
Conference Papers Year : 2021

Interactive Optimization of Submodular Functions under Matroid Constraints

Nawal Benabbou
Cassandre Leroy
  • Function : Author
  • PersonId : 1219036
  • IdRef : 267866623
Thibaut Lust
Patrice Perny


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.
Fichier principal
Vignette du fichier
ADT2021.pdf (356.32 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03953971 , version 1 (24-01-2023)



Nawal Benabbou, Cassandre Leroy, Thibaut Lust, Patrice Perny. Interactive Optimization of Submodular Functions under Matroid Constraints. ADT 2021 - 7th International Conference on Algorithmic Decision Theory, Nov 2021, Toulouse, France. pp.307-322, ⟨10.1007/978-3-030-87756-9_20⟩. ⟨hal-03953971⟩
26 View
22 Download



Gmail Mastodon Facebook X LinkedIn More