Home  ›  Continuous Greedy Algorithm Submodular Maximization Subject to a Mtroid

Continuous Greedy Algorithm Submodular Maximization Subject to a Mtroid

Written By Saturday, 15 October 2022 Add Comment Edit

Abstract

In this paper, we consider the problem of maximizing a non-submodular set function subject to a matroid constraint with the continuous generic submodularity ratio \(\gamma \). It quantifies how close a monotone function is to being submodular. As our main contribution, we propose a \((1-e^{-\gamma ^2}-O(\varepsilon ))\)-approximation algorithm when the submodularity ratio is sufficiently large. Our work also can be seen as the first extension of the adaptive sequencing technique in non-submodular case.

Keywords

  • Non-submodular optimization
  • Matroid constraint
  • Submodularity ratio
  • Adaptive sequencing

References

  1. Altschuler, J., Bhaskara, A., Fu, G., Mirrokni, V., Rostamizadeh, A., Zadimoghaddam, M.: Greedy column subset selection: new bounds and distributed algorithms. In: Proceedings of ICML, pp. 2539–2548 (2016)

    Google Scholar

  2. Alon, N., Spencer, J.H.: The Probabilistic Method, vol. 3, pp. 307–314. Wiley, New York (2008)

    Google Scholar

  3. Balkanski, E., Rubinstein, A., Singer, Y.: An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In: Proceedings of STOC, pp. 66–77 (2019)

    Google Scholar

  4. Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of ICML, pp. 498–507 (2017)

    Google Scholar

  5. Buchbinder, N., Feldman, M., Garg, M.: Deterministic (1/2+\(\varepsilon \))-approximation for submodular maximization over a matroid. In: Proceedings of SODA, pp. 241–254 (2019)

    Google Scholar

  6. C\(\breve{\rm a}\)linescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40, 1740–1766 (2011)

    Google Scholar

  7. Chekuri, C., Jayram, T.S., Vondrák, J.: On multiplicative weight updates for concave and submodular function maximization. In: Proceedings of ITCS, pp. 201–210 (2015)

    Google Scholar

  8. Chekuri, C., Quanrud, K.: Submodular function maximization in parallel via the multilinear relaxation. In: Proceedings of SODA, pp. 303–322 (2019)

    Google Scholar

  9. Chekuri, C., Vondrák, J., Zenklusen, R.: Dependent randomized rounding for matroid polytopes and applications. In: Proceedings of FOCS, pp. 575–584 (2010)

    Google Scholar

  10. Chen, L., Feldman, M., Karbasi, A.: Weakly submodular maximization beyond cardinality constraints: does randomization help greedy? In: Proceedings of ICML, pp. 804–813 (2018)

    Google Scholar

  11. Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of ICML, pp. 1057–1064 (2011)

    Google Scholar

  12. Edmonds, J.: Submodular functions, matroids, and certain polyhedra. Comb. Optim. 2570, 11–26 (2003)

    MathSciNet  MATH  Google Scholar

  13. Feige, U.: A threshold of \(\ln n\) for approximating set cover. J. ACM 45, 634–652 (1998)

    MathSciNet  CrossRef  Google Scholar

  14. Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: Proceedings of FOCS, pp. 570–579 (2011)

    Google Scholar

  15. Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions-II. Math. Program. Stud. 8, 73–87 (1978)

    MathSciNet  CrossRef  Google Scholar

  16. Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43, 514–542 (2014)

    MathSciNet  CrossRef  Google Scholar

  17. Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: Proceedings of ICML, pp. 2634–2643 (2019)

    Google Scholar

  18. Krause, A., Singh, A., Guestrin, C.: Nearoptimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235–284 (2008)

    MATH  Google Scholar

  19. Lawrence, N., Seeger, M., Herbrich, R.: Fast sparse Gaussian process methods: the informative vector machine. Adv. Neural Inf. Process. Syst. 1, 625–632 (2003)

    Google Scholar

  20. Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3, 177–188 (1978)

    MathSciNet  CrossRef  Google Scholar

  21. Rafiey, A., Yoshida, Y.: Fast and private submodular and \(k\)-submodular functions maximization with matroid constraints. arXiv:2006.15744 (2020)

  22. Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of STOC, pp. 67–74 (2008)

    Google Scholar

  23. Vondrák, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proceedings of STOC, pp. 783–792 (2011)

    Google Scholar

Download references

Acknowledgements

The first and second authors are supported by Beijing Natural Science Foundation Project (No. Z200002) and National Natural Science Foundation of China (No. 11871081). The third author is supported by National Natural Science Foundation of China (No. 11871081). The fourth author is supported by Natural Science Foundation of Shandong Province of China (No. ZR2019PA004) and National Natural Science Foundation of China (No. 12001335).

Author information

Authors and Affiliations

  1. Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing, 100124, People's Republic of China

    Xin Sun & Dachuan Xu

  2. School of Computer Science and Technology, Shandong Jianzhu University, Jinan, 250101, People's Republic of China

    Dongmei Zhang

  3. School of Mathematics and Statistics, Shandong Normal University, Jinan, 250014, People's Republic of China

    Yang Zhou

Corresponding author

Correspondence to Yang Zhou .

Editor information

Editors and Affiliations

  1. University of South Florida, Tampa, FL, USA

    Sriram Chellappan

  2. The University of Texas at San Antonio, San Antonio, TX, USA

    Prof. Kim-Kwang Raymond Choo

  3. New Jersey Institute of Technology, Newark, NJ, USA

    NhatHai Phan

Rights and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Verify currency and authenticity via CrossMark

Cite this paper

Sun, X., Xu, D., Zhang, D., Zhou, Y. (2020). An Adaptive Algorithm for Maximization of Non-submodular Function with a Matroid Constraint. In: Chellappan, S., Choo, KK.R., Phan, N. (eds) Computational Data and Social Networks. CSoNet 2020. Lecture Notes in Computer Science(), vol 12575. Springer, Cham. https://doi.org/10.1007/978-3-030-66046-8_1

Download citation

  • .RIS
  • .ENW
  • .BIB

  • DOI : https://doi.org/10.1007/978-3-030-66046-8_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-66045-1

  • Online ISBN: 978-3-030-66046-8

  • eBook Packages: Computer Science Computer Science (R0)

mcmullinmounten.blogspot.com

Source: https://link.springer.com/chapter/10.1007/978-3-030-66046-8_1

0 Response to "Continuous Greedy Algorithm Submodular Maximization Subject to a Mtroid"

Post a Comment

Subscribe to: Post Comments (Atom)

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel