Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/109189
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Friedrich, T. | - |
dc.contributor.author | Neumann, F. | - |
dc.contributor.editor | Bartz-Beielstein, T. | - |
dc.contributor.editor | Branke, J. | - |
dc.contributor.editor | Filipic, B. | - |
dc.contributor.editor | Smith, J. | - |
dc.date.issued | 2014 | - |
dc.identifier.citation | Lecture Notes in Artificial Intelligence, 2014 / Bartz-Beielstein, T., Branke, J., Filipic, B., Smith, J. (ed./s), vol.8672, pp.922-931 | - |
dc.identifier.isbn | 978-3-319-10761-5 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.issn | 1611-3349 | - |
dc.identifier.uri | http://hdl.handle.net/2440/109189 | - |
dc.description.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). | - |
dc.description.statementofresponsibility | Tobias Friedrich and Frank Neumann | - |
dc.language.iso | en | - |
dc.publisher | Springer | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science (LNCS, vol. 8672) | - |
dc.rights | © Springer International Publishing Switzerland 2014 | - |
dc.source.uri | http://dx.doi.org/10.1007/978-3-319-10762-2 | - |
dc.title | Maximizing submodular functions under matroid constraints by multi-objective evolutionary algorithms | - |
dc.type | Conference paper | - |
dc.contributor.conference | 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (13 Sep 2014 - 17 Sep 2014 : Ljubljana, Slovenia) | - |
dc.identifier.doi | 10.1007/978-3-319-10762-2_91 | - |
dc.relation.grant | http://purl.org/au-research/grants/arc/DP140103400 | - |
pubs.publication-status | Published | - |
dc.identifier.orcid | Neumann, F. [0000-0002-2721-3618] | - |
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.