Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/109189
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Maximizing submodular functions under matroid constraints by multi-objective evolutionary algorithms |
Author: | Friedrich, T. Neumann, F. |
Citation: | Lecture Notes in Artificial Intelligence, 2014 / Bartz-Beielstein, T., Branke, J., Filipic, B., Smith, J. (ed./s), vol.8672, pp.922-931 |
Publisher: | Springer |
Issue Date: | 2014 |
Series/Report no.: | Lecture Notes in Computer Science (LNCS, vol. 8672) |
ISBN: | 978-3-319-10761-5 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (13 Sep 2014 - 17 Sep 2014 : Ljubljana, Slovenia) |
Editor: | Bartz-Beielstein, T. Branke, J. Filipic, B. Smith, J. |
Statement of Responsibility: | Tobias Friedrich and Frank Neumann |
Abstract: | Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a multi-objective evolutionary algorithm called GSEMO until it has obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints we show that GSEMO achieves a (1 - 1/e)-approximation in expected time O(n2 (log n + k)), where k is the value of the given constraint. For the case of non-monotone submodular functions with k matroid intersection constraints, we show that GSEMO achieves a 1/(k +2+1/k + epsilon)-approximation in expected time O(nk+5 log(n)/epsilon). |
Rights: | © Springer International Publishing Switzerland 2014 |
DOI: | 10.1007/978-3-319-10762-2_91 |
Grant ID: | http://purl.org/au-research/grants/arc/DP140103400 |
Published version: | http://dx.doi.org/10.1007/978-3-319-10762-2 |
Appears in Collections: | Aurora harvest 8 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_109189.pdf Restricted Access | Restricted Access | 218.33 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.