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 FieldValueLanguage
dc.contributor.authorFriedrich, T.-
dc.contributor.authorNeumann, F.-
dc.contributor.editorBartz-Beielstein, T.-
dc.contributor.editorBranke, J.-
dc.contributor.editorFilipic, B.-
dc.contributor.editorSmith, J.-
dc.date.issued2014-
dc.identifier.citationLecture Notes in Artificial Intelligence, 2014 / Bartz-Beielstein, T., Branke, J., Filipic, B., Smith, J. (ed./s), vol.8672, pp.922-931-
dc.identifier.isbn978-3-319-10761-5-
dc.identifier.issn0302-9743-
dc.identifier.issn1611-3349-
dc.identifier.urihttp://hdl.handle.net/2440/109189-
dc.description.abstractMany 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.statementofresponsibilityTobias Friedrich and Frank Neumann-
dc.language.isoen-
dc.publisherSpringer-
dc.relation.ispartofseriesLecture Notes in Computer Science (LNCS, vol. 8672)-
dc.rights© Springer International Publishing Switzerland 2014-
dc.source.urihttp://dx.doi.org/10.1007/978-3-319-10762-2-
dc.titleMaximizing submodular functions under matroid constraints by multi-objective evolutionary algorithms-
dc.typeConference paper-
dc.contributor.conference13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (13 Sep 2014 - 17 Sep 2014 : Ljubljana, Slovenia)-
dc.identifier.doi10.1007/978-3-319-10762-2_91-
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140103400-
pubs.publication-statusPublished-
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]-
Appears in Collections:Aurora harvest 8
Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_109189.pdf
  Restricted Access
Restricted Access218.33 kBAdobe PDFView/Open


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