Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/128129
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Maximizing submodular or monotone functions under partition matroid constraints by multi-objective evolutionary algorithms |
Author: | Do, V. Neumann, F. |
Citation: | Lecture Notes in Artificial Intelligence, 2020 / Bäck, T., Preuss, M., Deutz, A.H., Wang, H., Doerr, C., Emmerich, M.T.M., Trautmann, H. (ed./s), vol.12270, pp.588-603 |
Publisher: | Springer Nature |
Publisher Place: | Switzerland |
Issue Date: | 2020 |
Series/Report no.: | Lecture Notes in Computer Science; 12270 |
ISBN: | 9783030581145 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Parallel Problem Solving from Nature (PPSN) (5 Sep 2020 - 9 Sep 2020 : Leiden, The Netherlands) |
Editor: | Bäck, T. Preuss, M. Deutz, A.H. Wang, H. Doerr, C. Emmerich, M.T.M. Trautmann, H. |
Statement of Responsibility: | Anh Viet Do and Frank Neumann |
Abstract: | Many important problems can be regarded as maximizing submodular functions under some constraints. A simple multi-objective evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. While there have been many studies on the subject, most of existing run-time analyses for GSEMO assume a single cardinality constraint. In this work, we extend the theoretical results to partition matroid constraints which generalize cardinality constraints, and show that GSEMO can generally guarantee good approximation performance within polynomial expected run time. Furthermore, we conducted experimental comparison against a baseline GREEDY algorithm in maximizing undirected graph cuts on random graphs, under various partition matroid constraints. The results show GSEMO tends to outperform GREEDY in quadratic run time. |
Keywords: | Evolutionary algorithms; Multi-objective evolutionary algorithms; Run-time analysis |
Rights: | © Springer Nature Switzerland AG 2020 |
DOI: | 10.1007/978-3-030-58115-2_41 |
Published version: | https://link.springer.com/book/10.1007/978-3-030-58115-2 |
Appears in Collections: | Aurora harvest 4 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.