{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T14:08:30Z","timestamp":1745849310795},"publisher-location":"Cham","reference-count":11,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_18","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:04:39Z","timestamp":1495544679000},"page":"212-227","source":"Crossref","is-referenced-by-count":5,"title":["Discrete Newton\u2019s Algorithm for Parametric Submodular Function Minimization"],"prefix":"10.1007","author":[{"given":"Michel X.","family":"Goemans","sequence":"first","affiliation":[]},{"given":"Swati","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Patrick","family":"Jaillet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"18_CR1","unstructured":"Freund, R.M., Grigas, P., Mazumder, R.: An extended Frank-Wolfe method with \u201cIn-Face\" directions, its application to low-rank matrix completion (2015). \narXiv:1511.02204"},{"issue":"3","key":"18_CR2","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1137\/S0895480192235878","volume":"7","author":"J H\u00e5stad","year":"1994","unstructured":"H\u00e5stad, J.: On the size of weights for threshold gates. SIAM J. Discrete Math. 7(3), 484\u2013492 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"18_CR3","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","volume":"112","author":"S Iwata","year":"2008","unstructured":"Iwata, S.: Submodular function minimization. Math. Program. 112(1), 45\u201364 (2008)","journal-title":"Math. Program."},{"issue":"4","key":"18_CR4","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1287\/moor.22.4.803","volume":"22","author":"S Iwata","year":"1997","unstructured":"Iwata, S., Murota, K., Shigeno, M.: A fast parametric submodular intersection algorithm for strong map sequences. Math. Oper. Res. 22(4), 803\u2013813 (1997)","journal-title":"Math. Oper. Res."},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Iwata, S., Orlin, J.B.: A simple combinatorial algorithm for submodular function minimization. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1230\u20131237. Society for Industrial and Applied Mathematics (2009)","DOI":"10.1137\/1.9781611973068.133"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.: A faster cutting plane method and its implications for combinatorial and convex optimization. In: Foundations of Computer Science (FOCS), pp. 1049\u20131065. IEEE (2015)","DOI":"10.1109\/FOCS.2015.68"},{"issue":"1","key":"18_CR7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0166-218X(92)00188-R","volume":"52","author":"ST McCormick","year":"1994","unstructured":"McCormick, S.T., Ervolina, T.R.: Computing maximum mean cuts. Discrete Appl. Math. 52(1), 53\u201370 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"18_CR8","doi-asserted-by":"crossref","first-page":"1460","DOI":"10.1137\/S0097539794282930","volume":"28","author":"K Mulmuley","year":"1999","unstructured":"Mulmuley, K.: Lower bounds in a parallel model without bit operations. SIAM J. Comput. 28(4), 1460\u20131509 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"18_CR9","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/j.disopt.2007.09.002","volume":"4","author":"K Nagano","year":"2007","unstructured":"Nagano, K.: A strongly polynomial algorithm for line search in submodular polyhedra. Discrete Optim. 4(3), 349\u2013359 (2007)","journal-title":"Discrete Optim."},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/978-1-4613-0303-9_6","volume-title":"Handbook of Combinatorial Optimization","author":"T Radzik","year":"1998","unstructured":"Radzik, T.: Fractional combinatorial optimization. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 429\u2013478. Springer, Heidelberg (1998)"},{"issue":"2","key":"18_CR11","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1287\/opre.26.2.305","volume":"26","author":"DM Topkis","year":"1978","unstructured":"Topkis, D.M.: Minimizing a submodular function on a lattice. Oper. Res. 26(2), 305\u2013321 (1978)","journal-title":"Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:08:37Z","timestamp":1495544917000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}