{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:16:45Z","timestamp":1762273005068,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T00:00:00Z","timestamp":1671235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T00:00:00Z","timestamp":1671235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971376"],"award-info":[{"award-number":["11971376"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s10957-022-02145-5","type":"journal-article","created":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T13:07:22Z","timestamp":1671282442000},"page":"516-543","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Greedy Guarantees for Non-submodular Function Maximization Under Independent System Constraint with Applications"],"prefix":"10.1007","volume":"196","author":[{"given":"Majun","family":"Shi","sequence":"first","affiliation":[]},{"given":"Zishen","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,17]]},"reference":[{"key":"2145_CR1","unstructured":"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, pp. 498\u2013507 (2017)"},{"issue":"3","key":"2145_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti, M., Cornu\u00e9jols, G.: Submodular functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3), 251\u2013274 (1984)","journal-title":"Discrete Appl. Math."},{"key":"2145_CR3","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Proceedings of the 12th Conference on Integer Programming and Combinatorial Optimization, vol. 4513, pp. 182\u2013196 (2007)","DOI":"10.1007\/978-3-540-72792-7_15"},{"issue":"6","key":"2145_CR4","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"2145_CR5","unstructured":"Chen, L., Feldman, M., Karbasi, A.: Weakly submodular maximization beyond cardinality constraints: does randomization help greedy? In: Proceedings of the 35th International Conference on Machine Learning, pp. 804\u2013813 (2018)"},{"key":"2145_CR6","unstructured":"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\u20131064 (2011)"},{"key":"2145_CR7","volume-title":"Design and Analysis of Approximation Algorithms","author":"DZ Du","year":"2012","unstructured":"Du, D.Z., Ko, K.I., Hu, X.D.: Design and Analysis of Approximation Algorithms. Springer, New York (2012)"},{"issue":"6B","key":"2145_CR8","first-page":"3539","volume":"46","author":"ER Elenberg","year":"2016","unstructured":"Elenberg, E.R., Khanna, R., Dimakis, A.G., Negahban, S.: Restricted strong convexity implies weak submodularity. Ann. Stat. 46(6B), 3539\u20133568 (2016)","journal-title":"Ann. Stat."},{"key":"2145_CR9","unstructured":"Feldman, M., Harshaw, C., Karbasi, A.: Greed is good: near-optimal submodular maximization via greedy optimization. In: Proceedings of the 30th Conference on Learning Theory, vol. 65, pp. 758\u2013784 (2017)"},{"issue":"2","key":"2145_CR10","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1137\/130920277","volume":"43","author":"Y Filmus","year":"2013","unstructured":"Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2), 514\u2013542 (2013)","journal-title":"SIAM J. Comput."},{"key":"2145_CR11","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions-II. Math. Program. Study 8, 73\u201387 (1978)","journal-title":"Math. Program. Study"},{"key":"2145_CR12","unstructured":"Gatmiry, K., Rodriguez, M.G.: Non-submodular function maximization subject to a matroid constraint, with applications (2018). arXiv:1811.07863v4"},{"key":"2145_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: offline and secretary algorithms. In: Proceedings of the 6th International Workshop on Internet and Network Economics, vol. 6484, pp. 246\u2013257 (2010)","DOI":"10.1007\/978-3-642-17572-5_20"},{"issue":"2","key":"2145_CR14","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1080\/00029890.2004.11920060","volume":"111","author":"S-G Hwang","year":"2004","unstructured":"Hwang, S.-G.: Cauchy\u2019s interlace theorem for eigenvalues of Hermitian matrices. Am. Math. Mon. 111(2), 157\u2013159 (2004)","journal-title":"Am. Math. Mon."},{"issue":"421","key":"2145_CR15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0167-5060(08)70322-4","volume":"2","author":"B Korte","year":"1978","unstructured":"Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. Ann. Discrete Math. 2(421), 65\u201374 (1978)","journal-title":"Ann. Discrete Math."},{"key":"2145_CR16","doi-asserted-by":"crossref","unstructured":"Kulesza, A., Taskar, B.: Determinantal point processes for machine learning. Found. Trends\u00ae\u00a0Mach. Learn. 5(2\u20133), 123\u2013286 (2012)","DOI":"10.1561\/2200000044"},{"issue":"4","key":"2145_CR17","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1137\/090750020","volume":"23","author":"J Lee","year":"2010","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing non-monotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math. 23(4), 2053\u20132078 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"2145_CR18","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the 41st ACM-SIAM Symposium on Theory of Computing, pp. 323\u2013332 (2009)","DOI":"10.1145\/1536414.1536459"},{"issue":"1","key":"2145_CR19","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"1","key":"2145_CR20","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/s10878-020-00672-3","volume":"41","author":"MJ Shi","year":"2021","unstructured":"Shi, M.J., Yang, Z.S., Kim, D.Y., Wang, W.: Non-monotone submodular function maximization under $$k$$-system constraint. J. Comb. Optim. 41(1), 128\u20131421 (2021)","journal-title":"J. Comb. Optim."},{"key":"2145_CR21","doi-asserted-by":"crossref","unstructured":"Sviridenko, M., Vondr\u00e1k, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. In: Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 1134\u20131148 (2015)","DOI":"10.1137\/1.9781611973730.76"},{"key":"2145_CR22","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th ACM Symposium on Theory of Computing, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"},{"key":"2145_CR23","first-page":"253","volume":"B23","author":"J Vondr\u00e1k","year":"2009","unstructured":"Vondr\u00e1k, J.: Submodularity and curvature: the optimal algorithm. RIMS Kokyuroku Bessatsu B23, 253\u2013266 (2009)","journal-title":"RIMS Kokyuroku Bessatsu"},{"issue":"05","key":"2145_CR24","doi-asserted-by":"crossref","first-page":"2140001","DOI":"10.1142\/S0217595921400017","volume":"38","author":"YJ Wang","year":"2021","unstructured":"Wang, Y.J., Du, D.L., Jiang, Y.J., Zhang, X.Z.: Non-submodular maximization with matroid and knapsack constraints. Asia Pac. J. Oper. Res. 38(05), 2140001 (2021)","journal-title":"Asia Pac. J. Oper. Res."},{"key":"2145_CR25","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s10898-019-00840-8","volume":"76","author":"YJ Wang","year":"2020","unstructured":"Wang, Y.J., Xu, D.C., Wang, Y.S., Zhang, D.M.: Non-submodular maximization on massive data streams. J. Glob. Optim. 76, 729\u2013743 (2020)","journal-title":"J. Glob. Optim."},{"key":"2145_CR26","doi-asserted-by":"crossref","unstructured":"Zhang, Z.N., Liu, B., Wang, Y.S., Xu, D.C., Zhang, D.M.: Greedy algorithm for maximization of non-submodular functions subject to knapsack constraint. In: Proceedings of the 26th International Computing and Combinatorics Conference, pp. 651\u2013662 (2019)","DOI":"10.1007\/978-3-030-26176-4_54"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-022-02145-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-022-02145-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-022-02145-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T06:40:35Z","timestamp":1676616035000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-022-02145-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,17]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["2145"],"URL":"https:\/\/doi.org\/10.1007\/s10957-022-02145-5","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2022,12,17]]},"assertion":[{"value":"22 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}