{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:44:55Z","timestamp":1742913895087,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030271947"},{"type":"electronic","value":"9783030271954"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-27195-4_23","type":"book-chapter","created":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T09:03:14Z","timestamp":1564650194000},"page":"249-260","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Maximize a Monotone Function with a Generic Submodularity Ratio"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0895-7793","authenticated-orcid":false,"given":"Qingqin","family":"Nong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suning","family":"Gong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qizhi","family":"Fang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7345-2185","authenticated-orcid":false,"given":"Dingzhu","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyu","family":"Shao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,1]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Harvey, N.J.A.: Learning submodular functions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 793\u2013802. ACM, San Jose (2011)","DOI":"10.1145\/1993636.1993741"},{"key":"23_CR2","unstructured":"Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: International Conference on Machine Learning, pp. 498\u2013507 (2017)"},{"issue":"3","key":"23_CR3","doi-asserted-by":"publisher","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 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\u2013274 (1984)","journal-title":"Discret. Appl. Math."},{"key":"23_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 182\u2013196. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72792-7_15"},{"key":"23_CR5","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 International Conference on Machine Learning, pp. 1057\u20131064, Omni press, Bellevue (2011)"},{"issue":"4","key":"23_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"23_CR7","doi-asserted-by":"publisher","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":"23_CR8","doi-asserted-by":"crossref","unstructured":"Filmus, Y., Ward, J.: A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In: the 53rd Annual Symposium on Foundations of Computer Science Foundations of Computer Science (FOCS), pp. 659\u2013668, IEEE, New Brunswick (2012)","DOI":"10.1109\/FOCS.2012.55"},{"issue":"1","key":"23_CR9","first-page":"269","volume":"69","author":"DS Hochbaum","year":"1995","unstructured":"Hochbaum, D.S., Hong, S.P.: About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Program. 69(1), 269\u2013309 (1995)","journal-title":"Math. Program."},{"issue":"4","key":"23_CR10","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1145\/502090.502093","volume":"48","author":"DS Hochbaum","year":"2001","unstructured":"Hochbaum, D.S.: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48(4), 686\u2013701 (2001)","journal-title":"J. ACM"},{"key":"23_CR11","first-page":"341","volume":"17","author":"T Jenkyns","year":"1976","unstructured":"Jenkyns, T.: The efficacy of the greedy algorithm. Cong. Num. 17, 341\u2013350 (1976)","journal-title":"Cong. Num."},{"issue":"1","key":"23_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.S.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"23_CR13","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, A., Guestrin, C.: Nearoptimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235\u2013284 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"23_CR14","unstructured":"Lawrence, N., Seeger, M., Herbrich, R.: Fast sparse Gaussian process methods: the informative vector machine. In: Advances in Neural Information Processing Systems, vol. 15, pp. 625\u2013632 (2003)"},{"issue":"4","key":"23_CR15","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795\u2013806 (2010)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"23_CR16","doi-asserted-by":"publisher","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":"3","key":"23_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177\u2013188 (1978)","journal-title":"Math. Oper. Res."},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Oper. Res. 7, 410\u2013425 (1982)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"23_CR19","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-27195-4_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:17:27Z","timestamp":1709824647000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-27195-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030271947","9783030271954"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-27195-4_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"1 August 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Applications in Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/theory.ict.ac.cn\/aaim2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}