Please use this identifier to cite or link to this item:
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: (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 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
Conference Name: 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (13 Sep 2014 - 17 Sep 2014 : Ljubljana, Slovenia)
Statement of
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
RMID: 0030042085
DOI: 10.1007/978-3-319-10762-2_91
Grant ID:
Published version:
Appears in Collections:Computer Science publications

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

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