Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Blood Leukocyte Object Detection According to Model Parameter-Transfer and Deformable Convolution Read chapter Read first chapter

2021 | OriginalPaper | Chapter

Submodular Maximization with Bounded Marginal Values

Authors : Ruiqi Yang, Suixiang Gao, Changjun Wang, Dongmei Zhang

Published in: Parallel and Distributed Computing, Applications and Technologies

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We study the problem of maximizing non-monotone submodular functions subject to a p-independence system constraint. Although the submodularity ratio has been well-studied in maximizing set functions under monotonic scenario, the defined parameter may bring hardness of approximation for the maximization of set functions in the non-monotonic case. In this work, utilizing a lower bound for the marginal values, we investigate the Repeated Greedy introduced by (Feldman et al. 2017) and obtain a parameterized performance guarantee for the above constrained submodular maximization problem.

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 Second-Order Convolutional Neural Network Based on Cholesky Compression Strategy
next chapter A Streaming Model for Monotone Lattice Submodular Maximization with a Cardinality Constraint
Literature
1.
Bai, W., Bilmes, J.: Greed is still good: maximizing monotone submodular \(+\) supermodular (BP) functions. In: Proceedings of the 35th International Conference on Machine Learning, pp. 314–323 (2018)
2.
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 498–507 (2017)
3.
Bogunovic, I., Zhao, J., Cevher, V.: Robust maximization of non-submodular objectives. In: Proceedings of the 21th International Conference on Artificial Intelligence and Statistics, pp. 890–899 (2018)
4.
Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3), 32 (2018)MathSciNetCrossRef
5.
Buchbinder, N., Feldman, M.: Constrained submodular maximization via a non-symmetric technique. Math. Oper. Res. 44(3), 988–1005 (2019)MathSciNetCrossRef
6.
Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time \(1/2\)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384–1402 (2015)MathSciNetCrossRef
7.
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. Discrete Appl. Math. 7(3), 251–274 (1984)MathSciNetCrossRef
8.
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 Machine Learning, pp. 1057–1064 (2011)
9.
10.
Feige, U., Izsak, R.: Welfare maximization and the supermodular degree. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 247–256 (2013)
11.
Feige, U., Mirrokni, V.S., Vondrák, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133–1153 (2011)MathSciNetCrossRef
12.
Feldman, M., Harshaw, C., Karbasi, A.: Greed is good: near-optimal submodular maximization via greedy optimization. In: Proceedings of the 30th Annual Conference on Learning Theory, pp. 758–784 (2017)
13.
Feldman, M., Izsak, R.: Constrained monotone function maximization and the supermodular degree. In: Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 18th International Workshop on Randomization and Computation, pp. 160–175 (2014)
14.
G\(\ddot{\rm o}\)lz, P., Procaccia, A.D.: Migration as submodular optimization. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 549–556 (2019)
15.
16.
Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: Offline and secretary algorithms. In: Proceedings of the 6th International Conference on Internet and Network Economics, pp. 246–257 (2010)
17.
Han, A., Cao, Z., Cui, S., Wu, B.: Deterministic approximation for submodular maximization over a matroid in nearly linear time, 2020, to appear in NeurIPS
18.
Hassidim, A., Singer, Y.: Optimization for approximate submodularity. In: Proceedings of the 32nd Annual Conference on Neural Information Processing Systems, pp. 396–407 (2018)
19.
Horel, T., Singer, Y.: Maximization of approximately submodular functions. In: Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 3053–3061 (2016)
20.
Jiang, Y., Wang, Y., Xu, D., Yang, R., Zhang, Y.: Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint. Optim. Lett. 13(82), 1–14 (2019)MATH
21.
Kuhnle, A., Smith, J.D., Crawford, V.G., Thai, M.T.: Fast maximization of non-submodular, monotonic functions on the integer lattice. In: Proceedings of the 35th International Conference on Machine Learning 2791–2800 (2018)
22.
Lee, J., Sviridenko, M., Vondrák, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795–806 (2010)MathSciNetCrossRef
23.
Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A.: Fast constrained submodular maximization: personalized data summarization. In: Proceedings of the 33rd International Conference on Machine Learning, pp. 1358–1366 (2016)
24.
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1), 265–294 (1978)MathSciNetCrossRef
25.
Qian, C., Shi, J., Yu, Y., Tang, K., Zhou, Z.: Subset selection under noise. In: Proceedings of the 31st Annual Conference on Neural Information Processing Systems, pp. 3560–3570 (2017)
26.
Sviridenko, M., Vondrák, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197–1218 (2017)MathSciNetCrossRef
27.
Metadata
Title
Submodular Maximization with Bounded Marginal Values
Authors
Ruiqi Yang
Suixiang Gao
Changjun Wang
Dongmei Zhang
Copyright Year
2021
Book
Parallel and Distributed Computing, Applications and Technologies

Print ISBN: 978-3-030-69243-8

Electronic ISBN: 978-3-030-69244-5

Copyright Year: 2021

DOI
https://doi.org/10.1007/978-3-030-69244-5_31

Premium Partner

    Image Credits