{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:41:11Z","timestamp":1764783671433,"version":"3.40.4"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319107615"},{"type":"electronic","value":"9783319107622"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-10762-2_91","type":"book-chapter","created":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T14:58:55Z","timestamp":1410361135000},"page":"922-931","source":"Crossref","is-referenced-by-count":16,"title":["Maximizing Submodular Functions under Matroid Constraints by Multi-objective Evolutionary Algorithms"],"prefix":"10.1007","author":[{"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2-3","key":"91_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00103-1","volume":"93","author":"A.A. Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.: An 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Applied Mathematics\u00a093(2-3), 149\u2013156 (1999)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"91_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1023\/A:1015059928466","volume":"1","author":"H.-G. Beyer","year":"2002","unstructured":"Beyer, H.-G., Schwefel, H.-P.: Evolution strategies \u2013 a comprehensive introduction. Natural Computing\u00a01(1), 3\u201352 (2002)","journal-title":"Natural Computing"},{"issue":"3","key":"91_CR3","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1162\/EVCO_a_00012","volume":"18","author":"K. Bringmann","year":"2010","unstructured":"Bringmann, K., Friedrich, T.: An efficient algorithm for computing hypervolume contributions. Evolutionary Computation\u00a018(3), 383\u2013402 (2010)","journal-title":"Evolutionary Computation"},{"key":"91_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1007\/978-3-319-10762-2_51","volume-title":"PPSN XIII 2014","author":"K. Bringmann","year":"2014","unstructured":"Bringmann, K., Friedrich, T., Klitzke, P.: Generic postprocessing via subset selection for hypervolume and epsilon-indicator. In: Bartz-Beielstein, T., et al. (eds.) PPSN XIII 2014. LNCS, vol.\u00a08672, pp. 518\u2013527. Springer, Heidelberg (2014)"},{"key":"91_CR5","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Friedrich, T., Klitzke, P.: Two-dimensional subset selection for hypervolume and epsilon-indicator. In: Annual Conference on Genetic and Evolutionary Computation (GECCO). ACM Press (2014b)","DOI":"10.1145\/2576768.2598276"},{"issue":"3","key":"91_CR6","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1109\/TEVC.2008.2009064","volume":"13","author":"D. Brockhoff","year":"2009","unstructured":"Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., Zitzler, E.: On the effects of adding objectives to plateau functions. IEEE Transactions on Evolutionary Computation\u00a013(3), 591\u2013603 (2009)","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"91_CR7","doi-asserted-by":"crossref","unstructured":"Cornuejols, G., Fisher, M., Nemhauser, G.L.: On the uncapacitated location problem. In: Studies in Integer Programming. Annals of Discrete Mathematics, vol.\u00a01, pp. 163\u2013177. Elsevier (1977)","DOI":"10.1016\/S0167-5060(08)70732-5"},{"key":"91_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, B., Kodric, B., Voigt, M.: Lower bounds for the runtime of a global multi-objective evolutionary algorithm. In: IEEE Congress on Evolutionary Computation (CEC), pp. 432\u2013439 (2013)","DOI":"10.1109\/CEC.2013.6557601"},{"issue":"4","key":"91_CR9","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"91_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U., Goemans, M.X.: Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT. In: 3rd Israel Symposium on Theory and Computing Systems (ISTCS), pp. 182\u2013189 (1995)","DOI":"10.1109\/ISTCS.1995.377033"},{"issue":"4","key":"91_CR11","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1162\/EVCO_a_00003","volume":"18","author":"T. Friedrich","year":"2010","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation\u00a018(4), 617\u2013633 (2010)","journal-title":"Evolutionary Computation"},{"key":"91_CR12","doi-asserted-by":"crossref","unstructured":"Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1918\u20131925 (2003)","DOI":"10.1109\/CEC.2003.1299908"},{"issue":"3","key":"91_CR13","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1162\/EVCO_a_00013","volume":"18","author":"O. Giel","year":"2010","unstructured":"Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation\u00a018(3), 335\u2013356 (2010)","journal-title":"Evolutionary Computation"},{"key":"91_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/978-3-319-10762-2_56","volume-title":"PPSN XIII 2014","author":"T. Glasmachers","year":"2014","unstructured":"Glasmachers, T.: Optimized approximation sets of low-dimensional benchmark pareto fronts. In: Bartz-Beielstein, T., et al. (eds.) PPSN XIII 2014. LNCS, vol.\u00a08672, pp. 569\u2013578. Springer, Heidelberg (2014)"},{"issue":"6","key":"91_CR15","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"91_CR16","unstructured":"Halperin, E., Zwick, U.: Combinatorial approximation algorithms for the maximum directed cut problem. In: Twelfth Annual Symposium on Discrete Algorithms (SODA), pp. 1\u20137 (2001)"},{"key":"91_CR17","doi-asserted-by":"crossref","unstructured":"Hansen, N.: The CMA evolution strategy: a comparing review. In: Lozano, J., Larranaga, P., Inza, I., Bengoetxea, E. (eds.) Towards a New Evolutionary Computation. Advances in estimation of distribution algorithms, pp. 75\u2013102. Springer (2006)","DOI":"10.1007\/11007937_4"},{"issue":"4","key":"91_CR18","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"91_CR19","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM\u00a048(4), 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"91_CR20","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 4th edn. Springer (2007)"},{"issue":"4","key":"91_CR21","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1007\/s00453-012-9660-4","volume":"65","author":"S. Kratsch","year":"2013","unstructured":"Kratsch, S., Neumann, F.: Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica\u00a065(4), 754\u2013771 (2013)","journal-title":"Algorithmica"},{"key":"91_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-45712-7_5","volume-title":"Parallel Problem Solving from Nature - PPSN VII","author":"M. Laumanns","year":"2002","unstructured":"Laumanns, M., Thiele, L., Zitzler, E., Welzl, E., Deb, K.: Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In: Guerv\u00f3s, J.J.M., Adamidis, P.A., Beyer, H.-G., Fern\u00e1ndez-Villaca\u00f1as, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol.\u00a02439, pp. 44\u201353. Springer, Heidelberg (2002)"},{"key":"91_CR23","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Forty-First Annual ACM Symposium on Theory of Computing (STOC), pp. 323\u2013332 (2009)","DOI":"10.1145\/1536414.1536459"},{"issue":"4","key":"91_CR24","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00453-012-9616-8","volume":"64","author":"P.K. Lehre","year":"2012","unstructured":"Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica\u00a064(4), 623\u2013642 (2012)","journal-title":"Algorithmica"},{"key":"91_CR25","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Korte, B., Gr\u00f6tschel, M. (eds.) Mathematical Programming: The State of the Art. Springer (1983)","DOI":"10.1007\/978-3-642-68874-4_10"},{"issue":"1","key":"91_CR26","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G. Nemhauser","year":"1978","unstructured":"Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of approximations for maximizing submodular set functions I. Mathematical Programming\u00a014(1), 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"issue":"3","key":"91_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research\u00a03(3), 177\u2013188 (1978)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"91_CR28","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s11047-006-9004-x","volume":"5","author":"F. Neumann","year":"2006","unstructured":"Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Natural Computing\u00a05(3), 305\u2013319 (2006)","journal-title":"Natural Computing"},{"issue":"1","key":"91_CR29","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00453-008-9253-4","volume":"57","author":"J. Reichel","year":"2010","unstructured":"Reichel, J., Skutella, M.: Evolutionary algorithms and matroid optimization problems. Algorithmica\u00a057(1), 187\u2013206 (2010)","journal-title":"Algorithmica"},{"key":"91_CR30","unstructured":"Schrijver, A.: Combinatorial Optimization \u2013 Polyhedra and Efficiency. Springer (2003)"},{"key":"91_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-34413-8_17","volume-title":"Learning and Intelligent Optimization","author":"T. Ulrich","year":"2012","unstructured":"Ulrich, T., Thiele, L.: Bounding the effectiveness of hypervolume-based (\u03bc + \u03bb)-archiving algorithms. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, vol.\u00a07219, pp. 235\u2013249. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XIII"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-10762-2_91","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T15:28:34Z","timestamp":1746372514000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-10762-2_91"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319107615","9783319107622"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-10762-2_91","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}