Top

Published in:

2020 | OriginalPaper | Chapter

Maximizing Submodular or Monotone Functions Under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms

Authors : Anh Viet Do, Frank Neumann

Published in: Parallel Problem Solving from Nature – PPSN XVI

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Many important problems can be regarded as maximizing submodular functions under some constraints. A simple multi-objective evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. While there have been many studies on the subject, most of existing run-time analyses for GSEMO assume a single cardinality constraint. In this work, we extend the theoretical results to partition matroid constraints which generalize cardinality constraints, and show that GSEMO can generally guarantee good approximation performance within polynomial expected run time. Furthermore, we conducted experimental comparison against a baseline GREEDY algorithm in maximizing undirected graph cuts on random graphs, under various partition matroid constraints. The results show GSEMO tends to outperform GREEDY in quadratic run time.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Optimal Mutation Rates for the EA on OneMax

next chapter Lower Bounds for Non-elitist Evolutionary Algorithms via Negative Multiplicative Drift

Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Co., Inc., Singapore (2011)MATH

Balcan, M.F., Blum, A., Mansour, Y.: Item pricing for revenue maximization. In: Proceedings of the 9th ACM Conference on Electronic Commerce, EC 2008, pp. 50–59. ACM, New York (2008). https://doi.org/10.1145/1386790.1386802

Bhawalkar, K., Roughgarden, T.: Welfare guarantees for combinatorial auctions with item bidding. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 700–709. Society for Industrial and Applied Mathematics, Philadelphia (2011). https://doi.org/10.1137/1.9781611973082.55

Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017, vol. 70, pp. 498–507. JMLR.org (2017)

Buchbinder, N., Feldman, M., Garg, M.: Deterministic \((1/2 + \epsilon )\)-approximation for submodular maximization over a matroid. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pp. 241–254. Society for Industrial and Applied Mathematics, Philadelphia (2019)

Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX/RANDOM -2004. LNCS, vol. 3122, pp. 72–83. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27821-4_7CrossRefMATH

Conforti, M., Cornuéjols, G.: Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discret. Appl. Math. 7(3), 251–274 (1984). https://doi.org/10.1016/0166-218X(84)90003-9MathSciNetCrossRefMATH

Corder, G.W., Foreman, D.I.: Nonparametric Statistics for Non-Statisticians: A Step-by-Step Approach. Wiley, Hoboken (2009)CrossRef

Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23(8), 789–810 (1977). https://doi.org/10.1287/mnsc.23.8.789MathSciNetCrossRefMATH

10.

Călinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740–1766 (2011). https://doi.org/10.1137/080733991MathSciNetCrossRefMATH

11.

Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML 2011, Omnipress, Madison, WI, USA, pp. 1057–1064 (2011)

12.

Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation - Recent Developments in Discrete Optimization. Natural Computing Series. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4CrossRefMATH

13.

Feige, U., Mirrokni, V.S., Vondrák, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133–1153 (2011). https://doi.org/10.1137/090779346MathSciNetCrossRefMATH

14.

Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006, pp. 611–620. Society for Industrial and Applied Mathematics, Philadelphia (2006). https://doi.org/10.1145/1109557.1109624

15.

Friedrich, T., Göbel, A., Neumann, F., Quinzan, F., Rothenberger, R.: Greedy maximization of functions with bounded curvature under partition matroid constraints. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 2272–2279 (2019). https://doi.org/10.1609/aaai.v33i01.33012272

16.

Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models*. Evol. Comput. 18(4), 617–633 (2010). https://doi.org/10.1162/EVCO_a_00003CrossRef

17.

Friedrich, T., Neumann, F.: Maximizing submodular functions under matroid constraints by evolutionary algorithms. Evol. Comput. 23(4), 543–558 (2015). https://doi.org/10.1162/EVCO_a_00159CrossRef

18.

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). https://doi.org/10.1145/227683.227684MathSciNetCrossRefMATH

19.

Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761–777 (2001). https://doi.org/10.1145/502090.502096MathSciNetCrossRefMATH

20.

Jansen, T.: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-17339-4CrossRefMATH

21.

Jegelka, S., Bilmes, J.: Submodularity beyond submodular energies: coupling edges in graph cuts. In: CVPR 2011, pp. 1897–1904 (2011). https://doi.org/10.1109/CVPR.2011.5995589

22.

Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2003, pp. 137–146. ACM, New York (2003). https://doi.org/10.1145/956750.956769

23.

Krause, A., Guestrin, C.: Submodularity and its applications in optimized information gathering. ACM Trans. Intell. Syst. Technol. 2(4), 32:1–32:20 (2011). https://doi.org/10.1145/1989734.1989736CrossRef

24.

Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235–284 (2008). https://doi.org/10.1145/1390681.1390689CrossRefMATH

25.

Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functidons. IEEE Trans. Evol. Comput. 8(2), 170–182 (2004). https://doi.org/10.1109/TEVC.2004.823470CrossRefMATH

26.

Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 323–332. ACM, New York (2009). https://doi.org/10.1145/1536414.1536459

27.

Lengler, J.: Drift analysis. CoRR abs/1712.00964 (2017). http://arxiv.org/abs/1712.00964

28.

Lin, H., Bilmes, J.: Multi-document summarization via budgeted maximization of submodular functions. In: Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, HLT 2010, pp. 912–920. Association for Computational Linguistics, Cambridge (2010)

29.

Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, HLT 2011, pp. 510–520. Association for Computational Linguistics, Portland (2011)

30.

Liu, Y., Wei, K., Kirchhoff, K., Song, Y., Bilmes, J.: Submodular feature selection for high-dimensional acoustic score spaces. In: 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 7184–7188 (2013). https://doi.org/10.1109/ICASSP.2013.6639057

31.

Lovász, L.: Submodular functions and convexity. In: Bachem, A., Korte, B., Grotschel, M. (eds.) Mathematical Programming the State of the Art, pp. 235–257. Springer, Heidelberg (1983). https://doi.org/10.1007/978-3-642-68874-4_10CrossRef

32.

Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177–188 (1978). https://doi.org/10.1287/moor.3.3.177MathSciNetCrossRefMATH

33.

Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization. Natural Computing Series. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16544-3CrossRefMATH

34.

Qian, C., Shi, J.C., Yu, Y., Tang, K.: On subset selection with general cost constraints. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 2613–2619 (2017). https://doi.org/10.24963/ijcai.2017/364

35.

Qian, C., Shi, J.C., Yu, Y., Tang, K., Zhou, Z.H.: Parallel pareto optimization for subset selection. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, pp. 1939–1945. AAAI Press (2016)

36.

Qian, C., Yu, Y., Tang, K., Yao, X., Zhou, Z.H.: Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms. Artif. Intell. 275, 279–294 (2019). https://doi.org/10.1016/j.artint.2019.06.005MathSciNetCrossRefMATH

37.

Queyranne, M.: A combinatorial algorithm for minimizing symmetric submodular functions. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, pp. 98–101. Society for Industrial and Applied Mathematics, Philadelphia (1995)

38.

Stobbe, P., Krause, A.: Efficient minimization of decomposable submodular functions. In: Proceedings of the 23rd International Conference on Neural Information Processing Systems, NIPS 2010, vol. 2, pp. 2208–2216. Curran Associates Inc., New York (2010)

39.

Syrgkanis, V., Tardos, É.: Composable and efficient mechanisms. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 211–220. ACM, New York (2013). https://doi.org/10.1145/2488608.2488635

40.

Vondrák, J.: Submodularity and curvature: the optimal algorithm. RIMS Kôkyûroku Bessatsu B23, pp. 253–266 (2010)

41.

Wei, K., Iyer, R., Bilmes, J.: Submodularity in data subset selection and active learning. In: Proceedings of the 32nd International Conference on International Conference on Machine Learning, ICML 2015, vol. 37, pp. 1954–1963. JMLR.org (2015)

42.

Zhou, Z., Yu, Y., Qian, C.: Evolutionary Learning: Advances in Theories and Algorithms. Springer, Singapore (2019). https://doi.org/10.1007/978-981-13-5956-9CrossRefMATH

Title: Maximizing Submodular or Monotone Functions Under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
Authors: Anh Viet Do
Frank Neumann
Publisher: Springer International Publishing
Book: Parallel Problem Solving from Nature – PPSN XVI
Print ISBN: 978-3-030-58114-5

Electronic ISBN: 978-3-030-58115-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-58115-2_41

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner