{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T10:07:55Z","timestamp":1742983675774,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319781983"},{"type":"electronic","value":"9783319781990"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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":[[2018]]},"DOI":"10.1007\/978-3-319-78199-0_29","type":"book-chapter","created":{"date-parts":[[2018,3,21]],"date-time":"2018-03-21T00:13:52Z","timestamp":1521591232000},"page":"439-454","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Slack and Margin Rescaling as Convex Extensions of Supermodular Functions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2640-181X","authenticated-orcid":false,"given":"Matthew B.","family":"Blaschko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,22]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. In: FOCS (2012)","DOI":"10.1109\/FOCS.2012.73"},{"key":"29_CR2","unstructured":"Choi, H., Meshi, O., Srebro, N.: Fast and scalable structural SVM with slack rescaling. In: AISTATS, pp. 667\u2013675 (2016)"},{"issue":"3","key":"29_CR3","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 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":"29_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer Programming. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11008-0"},{"key":"29_CR5","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Elsevier, Amsterdam (2005)"},{"key":"29_CR6","unstructured":"Iyer, R., Bilmes, J.: Algorithms for approximate minimization of the difference between submodular functions, with applications. In: UAI, pp. 407\u2013417 (2012)"},{"key":"29_CR7","unstructured":"Iyer, R.K., Bilmes, J.A.: Polyhedral aspects of submodularity, convexity and concavity. CoRR, abs\/1506.07329 (2015)"},{"key":"29_CR8","unstructured":"Iyer, R.K., Jegelka, S., Bilmes, J.A.: Curvature and optimal algorithms for learning and minimizing submodular functions. In: NIPS, pp. 2742\u20132750 (2013)"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Jegelka, S., Bilmes, J.A.: Submodularity beyond submodular energies: coupling edges in graph cuts. In: CVPR, pp. 1897\u20131904 (2011)","DOI":"10.1109\/CVPR.2011.5995589"},{"issue":"16\u201317","key":"29_CR10","doi-asserted-by":"crossref","first-page":"2419","DOI":"10.1016\/j.dam.2012.06.009","volume":"160","author":"F Kahl","year":"2012","unstructured":"Kahl, F., Strandmark, P.: Generalized roof duality. Discret. Appl. Math. 160(16\u201317), 2419\u20132434 (2012)","journal-title":"Discret. Appl. Math."},{"key":"29_CR11","volume-title":"Tractability: Practical Approaches to Hard Problems","author":"A Krause","year":"2014","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. In: Bordeaux, L., Hamadi, Y., Kohli, P. (eds.) Tractability: Practical Approaches to Hard Problems. Cambridge University Press, Cambridge (2014)"},{"key":"29_CR12","first-page":"71","volume":"10","author":"MP Kumar","year":"2009","unstructured":"Kumar, M.P., Kolmogorov, V., Torr, P.H.S.: An analysis of convex relaxations for MAP estimation of discrete MRFs. JMLR 10, 71\u2013106 (2009)","journal-title":"JMLR"},{"key":"29_CR13","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming The State of the Art","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Korte, B., Gr\u00f6tschel, M. (eds.) Mathematical Programming The State of the Art, pp. 235\u2013257. Springer, Berlin (1983). https:\/\/doi.org\/10.1007\/978-3-642-68874-4_10"},{"key":"29_CR14","volume-title":"Predicting Structured Data","author":"D McAllester","year":"2007","unstructured":"McAllester, D.: Generalization bounds and consistency for structured labeling. In: Bak\u0131r, G., Hofmann, T., Sch\u00f6lkopf, B., Smola, A., Taskar, B., Vishwanathan, S. (eds.) Predicting Structured Data. MIT Press, Cambridge (2007)"},{"issue":"1","key":"29_CR15","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. Prog. 14(1), 265\u2013294 (1978)","journal-title":"Math. Prog."},{"issue":"11","key":"29_CR16","doi-asserted-by":"crossref","first-page":"1958","DOI":"10.1109\/TPAMI.2008.128","volume":"30","author":"A Torralba","year":"2008","unstructured":"Torralba, A., Fergus, R., Freeman, W.T.: 80 million tiny images: a large data set for nonparametric object and scene recognition. PAMI 30(11), 1958\u20131970 (2008)","journal-title":"PAMI"},{"key":"29_CR17","first-page":"1453","volume":"6","author":"I Tsochantaridis","year":"2005","unstructured":"Tsochantaridis, I., Joachims, T., Hofmann, T., Altun, Y.: Large margin methods for structured and interdependent output variables. JMLR 6, 1453\u20131484 (2005)","journal-title":"JMLR"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"},{"key":"29_CR19","first-page":"253","volume":"23","author":"J Vondr\u00e1k","year":"2010","unstructured":"Vondr\u00e1k, J.: Submodularity and curvature: the optimal algorithm. RIMS K\u00f4ky\u00fbroku Bessatsu 23, 253\u2013266 (2010)","journal-title":"RIMS K\u00f4ky\u00fbroku Bessatsu"},{"key":"29_CR20","unstructured":"Weller, A., Sontag, D., Rowland, M.: Tightness of LP relaxations for almost balanced models. In: AISTATS, pp. 47\u201355 (2016)"},{"key":"29_CR21","unstructured":"Yu, J., Blaschko, M.B.: Learning submodular losses with the Lov\u00e1sz hinge. In: ICML, pp. 1623\u20131631 (2015)"},{"key":"29_CR22","unstructured":"Yu, J., Blaschko, M.B.: A convex surrogate operator for general non-modular loss functions. In: AISTATS, pp. 1032\u20131041 (2016)"}],"container-title":["Lecture Notes in Computer Science","Energy Minimization Methods in Computer Vision and Pattern Recognition"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-78199-0_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,13]],"date-time":"2019-10-13T01:54:09Z","timestamp":1570931649000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-78199-0_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319781983","9783319781990"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-78199-0_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}