Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Diversifying greedy sampling and evolutionary diversity optimisation for constrained monotone submodular functions
Author: Neumann, A.
Bossek, J.
Neumann, F.
Citation: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'21), 2021 / Chicano, F., Krawiec, K. (ed./s), pp.261-269
Publisher: Association for Computing Machinery
Publisher Place: New York, NY
Issue Date: 2021
ISBN: 9781450383509
Conference Name: Genetic and Evolutionary Computation Conference (GECCO) (10 Jul 2021 - 14 Jul 2021 : virtual online)
Editor: Chicano, F.
Krawiec, K.
Statement of
Aneta Neumann, Jakob Bossek, Frank Neumann
Abstract: Submodular functions allow to model many real-world optimisation problems. This paper introduces approaches for computing diverse sets of high quality solutions for submodular optimisation problems with uniform and knapsack constraints. We first present diversifying greedy sampling approaches and analyse them with respect to the diversity measured by entropy and the approximation quality of the obtained solutions. Afterwards, we introduce an evolutionary diversity optimisation (EDO) approach to further improve diversity of the set of solutions.We carry out experimental investigations on popular submodular benchmark problems and analyse trade-offs in terms of solution quality and diversity of the resulting solution sets.
Keywords: Evolutionary algorithms; evolutionary diversity optimisation; submodular functions
Rights: © 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.
DOI: 10.1145/3449639.3459385
Grant ID:
Published version:
Appears in Collections:Aurora harvest 8
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.