{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:13:03Z","timestamp":1767237183908},"reference-count":44,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p> 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 simple single objective evolutionary algorithm called ([Formula: see text]) EA and a multiobjective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints, we show that the GSEMO achieves a [Formula: see text]-approximation\u00a0in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of [Formula: see text] matroids, we show that the ([Formula: see text]) EA achieves a ([Formula: see text])-approximation in expected polynomial time for any constant [Formula: see text]. Turning to nonmonotone symmetric submodular functions with [Formula: see text]\u00a0matroid intersection constraints, we show that the GSEMO achieves a [Formula: see text]-approximation in expected time [Formula: see text]. <\/jats:p>","DOI":"10.1162\/evco_a_00159","type":"journal-article","created":{"date-parts":[[2015,7,2]],"date-time":"2015-07-02T14:23:56Z","timestamp":1435847036000},"page":"543-558","source":"Crossref","is-referenced-by-count":61,"title":["Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms"],"prefix":"10.1162","volume":"23","author":[{"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[{"name":"Hasso Plattner Institute, Potsdam, Germany"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Adelaide, Australia"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00103-1"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1887\/0750308958"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015059928466"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00012"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10762-2_51"},{"key":"B6","first-page":"589","author":"Bringmann K.","year":"2014","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2008.2009064"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70732-5"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2013.6557601"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00182-7"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00003"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10762-2_91"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1022"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2003.1299908"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00013"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10762-2_56"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1145\/2739480.2754812"},{"key":"B21","first-page":"1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms","author":"Halperin E.","year":"2001"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87700-4_4"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-32494-1_4"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703426775"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1023\/B:JMMA.0000049378.57591.c6"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44719-9_19"},{"key":"B29","author":"Korte B.","year":"2007","journal-title":"Combinatorial optimization: Theory and algorithms"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9660-4"},{"key":"B31","author":"Kuhn T.","year":"2014","journal-title":"Hypervolume subset selection in two dimensions: Formulations and algorithms."},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45712-7_5"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536459"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0463"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9616-8"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-006-9004-x"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9253-4"},{"key":"B41","author":"Rudolph G.","year":"1996","journal-title":"Convergence properties of evolutionary algorithms"},{"key":"B42","volume-title":"Combinatorial optimization: Polyhedra and efficiency","author":"Schrijver A","year":"2003"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34413-8_17"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.120"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00159","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:42Z","timestamp":1615586322000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/23\/4\/543-558\/1019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1162\/EVCO_a_00159"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00159","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}