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 \(\mathcal{O}(n^2\,(\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 + ε)-approximation in expected time \(\mathcal{O}(n^{k+5}\log (n) / \varepsilon )\).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Combinatorial Optimization Problem
- Submodular Function
- Oracle Access
- Evolutionary Multiobjective Optimization
- Hypervolume Indicator
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ageev, A.A., Sviridenko, M.: An 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Applied Mathematics 93(2-3), 149–156 (1999)
Beyer, H.-G., Schwefel, H.-P.: Evolution strategies – a comprehensive introduction. Natural Computing 1(1), 3–52 (2002)
Bringmann, K., Friedrich, T.: An efficient algorithm for computing hypervolume contributions. Evolutionary Computation 18(3), 383–402 (2010)
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. 8672, pp. 518–527. Springer, Heidelberg (2014)
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)
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 13(3), 591–603 (2009)
Cornuejols, G., Fisher, M., Nemhauser, G.L.: On the uncapacitated location problem. In: Studies in Integer Programming. Annals of Discrete Mathematics, vol. 1, pp. 163–177. Elsevier (1977)
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–439 (2013)
Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)
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–189 (1995)
Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation 18(4), 617–633 (2010)
Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1918–1925 (2003)
Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation 18(3), 335–356 (2010)
Glasmachers, T.: Optimized approximation sets of low-dimensional benchmark pareto fronts. In: Bartz-Beielstein, T., et al. (eds.) PPSN XIII 2014. LNCS, vol. 8672, pp. 569–578. Springer, Heidelberg (2014)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)
Halperin, E., Zwick, U.: Combinatorial approximation algorithms for the maximum directed cut problem. In: Twelfth Annual Symposium on Discrete Algorithms (SODA), pp. 1–7 (2001)
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–102. Springer (2006)
Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001)
Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761–777 (2001)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 4th edn. Springer (2007)
Kratsch, S., Neumann, F.: Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica 65(4), 754–771 (2013)
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ós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 44–53. Springer, Heidelberg (2002)
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–332 (2009)
Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64(4), 623–642 (2012)
Lovász, L.: Submodular functions and convexity. In: Bachem, A., Korte, B., Grötschel, M. (eds.) Mathematical Programming: The State of the Art. Springer (1983)
Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of approximations for maximizing submodular set functions I. Mathematical Programming 14(1), 265–294 (1978)
Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research 3(3), 177–188 (1978)
Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Natural Computing 5(3), 305–319 (2006)
Reichel, J., Skutella, M.: Evolutionary algorithms and matroid optimization problems. Algorithmica 57(1), 187–206 (2010)
Schrijver, A.: Combinatorial Optimization – Polyhedra and Efficiency. Springer (2003)
Ulrich, T., Thiele, L.: Bounding the effectiveness of hypervolume-based (μ + λ)-archiving algorithms. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, vol. 7219, pp. 235–249. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Friedrich, T., Neumann, F. (2014). Maximizing Submodular Functions under Matroid Constraints by Multi-objective Evolutionary Algorithms. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds) Parallel Problem Solving from Nature – PPSN XIII. PPSN 2014. Lecture Notes in Computer Science, vol 8672. Springer, Cham. https://doi.org/10.1007/978-3-319-10762-2_91
Download citation
DOI: https://doi.org/10.1007/978-3-319-10762-2_91
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10761-5
Online ISBN: 978-3-319-10762-2
eBook Packages: Computer ScienceComputer Science (R0)