Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions
A. Neumann, J. Bossek, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2021, pp. 261–269.
Download
No fulltext has been uploaded.
Conference Paper
| English
Author
Neumann, Aneta;
Bossek, JakobLibreCat 
;
Neumann, Frank
;
Neumann, FrankDepartment
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.
Publishing Year
Proceedings Title
Proceedings of the Genetic and Evolutionary Computation Conference
forms.conference.field.series_title_volume.label
GECCO’21
Page
261–269
ISBN
LibreCat-ID
Cite this
Neumann A, Bossek J, Neumann F. Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO’21. Association for Computing Machinery; 2021:261–269. doi:10.1145/3449639.3459385
Neumann, A., Bossek, J., & Neumann, F. (2021). Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions. Proceedings of the Genetic and Evolutionary Computation Conference, 261–269. https://doi.org/10.1145/3449639.3459385
@inproceedings{Neumann_Bossek_Neumann_2021, place={New York, NY, USA}, series={GECCO’21}, title={Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions}, DOI={10.1145/3449639.3459385}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Neumann, Aneta and Bossek, Jakob and Neumann, Frank}, year={2021}, pages={261–269}, collection={GECCO’21} }
Neumann, Aneta, Jakob Bossek, and Frank Neumann. “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions.” In Proceedings of the Genetic and Evolutionary Computation Conference, 261–269. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. https://doi.org/10.1145/3449639.3459385.
A. Neumann, J. Bossek, and F. Neumann, “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions,” in Proceedings of the Genetic and Evolutionary Computation Conference, 2021, pp. 261–269, doi: 10.1145/3449639.3459385.
Neumann, Aneta, et al. “Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions.” Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2021, pp. 261–269, doi:10.1145/3449639.3459385.
Google Scholar
ISBN Search