{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T11:48:33Z","timestamp":1769514513188,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":65,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055419","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"1220-1231","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Subquadratic submodular function minimization"],"prefix":"10.1145","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[{"name":"Dartmouth College, USA"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Sam Chiu-wai","family":"Wong","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2602000"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746566"},{"key":"e_1_3_2_2_3_1","volume-title":"Submodularity in Machine Learning Applications. Twenty-Ninth Conference on Artificial Intelligence, AAAI-15 Tutorial Forum. (January","author":"Bilmes Jeff","year":"2015","unstructured":"Jeff Bilmes . 2015 . Submodularity in Machine Learning Applications. Twenty-Ninth Conference on Artificial Intelligence, AAAI-15 Tutorial Forum. (January 2015). Jeff Bilmes. 2015. Submodularity in Machine Learning Applications. Twenty-Ninth Conference on Artificial Intelligence, AAAI-15 Tutorial Forum. (January 2015)."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.60"},{"key":"e_1_3_2_2_5_1","unstructured":"Yuri Boykov Olga Veksler and Ramin Zabih. 2001.  Yuri Boykov Olga Veksler and Ramin Zabih. 2001."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.969114"},{"key":"e_1_3_2_2_7_1","unstructured":"S\u00e9bastien Bubeck. 2015.  S\u00e9bastien Bubeck. 2015."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_3_2_2_10_1","unstructured":"Deeparnab Chakrabarty Prateek Jain and Pravesh Kothari. 2014.  Deeparnab Chakrabarty Prateek Jain and Pravesh Kothari. 2014."},{"key":"e_1_3_2_2_11_1","volume-title":"Proc. Sys. (NIPS)","author":"Provable Submodular","year":"2014","unstructured":"Provable Submodular Minimization via Fujishige-Wolfe Algorithm. Adv. in Neu. Inf . Proc. Sys. (NIPS) ( 2014 ). Provable Submodular Minimization via Fujishige-Wolfe Algorithm. Adv. in Neu. Inf. Proc. Sys. (NIPS) (2014)."},{"key":"e_1_3_2_2_12_1","unstructured":"Gustave Choquet. 1955.  Gustave Choquet. 1955."},{"key":"e_1_3_2_2_13_1","volume-title":"Annales de l\u2019institut Fourier 5","author":"Capacities Theory","year":"1955","unstructured":"Theory of Capacities . Annales de l\u2019institut Fourier 5 ( 1955 ), 131\u2013295. Theory of Capacities. Annales de l\u2019institut Fourier 5 (1955), 131\u2013295."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579361"},{"key":"e_1_3_2_2_15_1","unstructured":"Jack Edmonds. 1970.  Jack Edmonds. 1970."},{"key":"e_1_3_2_2_16_1","volume-title":"matroids and certain polyhedra. Combinatorial Structures and Their Applications","author":"Submodular","year":"1970","unstructured":"Submodular functions , matroids and certain polyhedra. Combinatorial Structures and Their Applications ( 1970 ), 69\u201387. Submodular functions, matroids and certain polyhedra. Combinatorial Structures and Their Applications (1970), 69\u201387."},{"key":"e_1_3_2_2_17_1","volume-title":"Nguyen","author":"Ene Alina","year":"2015","unstructured":"Alina Ene and Huy L . Nguyen . 2015 . Alina Ene and Huy L. Nguyen. 2015."},{"key":"e_1_3_2_2_18_1","volume-title":"Coordinate Descent Methods forMinimizing Decomposable Submodular Functions. Proc, Int. Conf. on Machine Leanring (ICML)","author":"Random","year":"2015","unstructured":"Random Coordinate Descent Methods forMinimizing Decomposable Submodular Functions. Proc, Int. Conf. on Machine Leanring (ICML) ( 2015 ). Random Coordinate Descent Methods forMinimizing Decomposable Submodular Functions. Proc, Int. Conf. on Machine Leanring (ICML) (2015)."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_3_2_2_20_1","unstructured":"Marguerite Frank and Philip Wolfe. 1956.  Marguerite Frank and Philip Wolfe. 1956."},{"key":"e_1_3_2_2_21_1","volume-title":"Naval Research Logistics Quarterly 3, 1-2","author":"An","year":"1956","unstructured":"An algorithm for quadratic programming. Naval Research Logistics Quarterly 3, 1-2 ( 1956 ), 95\u2013110. DOI: https:\/\/ An algorithm for quadratic programming. Naval Research Logistics Quarterly 3, 1-2 (1956), 95\u2013110. DOI: https:\/\/"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.2.186"},{"key":"e_1_3_2_2_23_1","unstructured":"Satoru Fujishige. 2005.  Satoru Fujishige. 2005."},{"key":"e_1_3_2_2_24_1","unstructured":"Submodular functions and optimization. Elsevier.  Submodular functions and optimization. Elsevier."},{"key":"e_1_3_2_2_25_1","volume-title":"The Minimum-Norm-Point Algorithm Applied to Submodular Function Minimization and linear programming","author":"Fujishige Satoru","unstructured":"Satoru Fujishige , Takumi Hayashi , and Shigueo Isotani . 2006. The Minimum-Norm-Point Algorithm Applied to Submodular Function Minimization and linear programming . Publications of the Research Institute for Mathematical Sciences (RIMS) , Kyoto. Satoru Fujishige, Takumi Hayashi, and Shigueo Isotani. 2006. The Minimum-Norm-Point Algorithm Applied to Submodular Function Minimization and linear programming. Publications of the Research Institute for Mathematical Sciences (RIMS), Kyoto."},{"key":"e_1_3_2_2_26_1","first-page":"3","article-title":"A Submodular Function Minimization Algorithm based on the Minimum-Norm Base","volume":"7","author":"Fujishige Satoru","year":"2011","unstructured":"Satoru Fujishige and Shigueo Isotani . 2011 . A Submodular Function Minimization Algorithm based on the Minimum-Norm Base . Pacific Journal of Optimization 7 (2011), 3 \u2013 17 . Satoru Fujishige and Shigueo Isotani. 2011. A Submodular Function Minimization Algorithm based on the Minimum-Norm Base. Pacific Journal of Optimization 7 (2011), 3\u201317.","journal-title":"Pacific Journal of Optimization"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/140985366"},{"key":"e_1_3_2_2_28_1","volume-title":"Soto","author":"Goemans Michel X.","year":"2013","unstructured":"Michel X. Goemans and Jose A . Soto . 2013 . Symmetric Submodular Function Minimization Under Hereditary Family Constraints . 27, 2 (2013), 1123 \u2013 1145. Michel X. Goemans and Jose A. Soto. 2013. Symmetric Submodular Function Minimization Under Hereditary Family Constraints. 27, 2 (2013), 1123 \u2013 1145."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_2_30_1","unstructured":"Nicholas James Alexander Harvey. 2008.  Nicholas James Alexander Harvey. 2008."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2503308.2503334"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"e_1_3_2_2_34_1","volume-title":"Orlin","author":"Iwata Satoru","year":"2009","unstructured":"Satoru Iwata and James B . Orlin . 2009 . A simple combinatorial algorithm for submodular function minimization. In SODA. 1230\u20131237. Satoru Iwata and James B. Orlin. 2009. A simple combinatorial algorithm for submodular function minimization. In SODA. 1230\u20131237."},{"key":"e_1_3_2_2_35_1","volume-title":"Proc. Sys. (NIPS)","author":"Iyer Rishabh","year":"2013","unstructured":"Rishabh Iyer and Jeff A. Bilmes . 2013. Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints. Adv. in Neu. Inf . Proc. Sys. (NIPS) ( 2013 ). Rishabh Iyer and Jeff A. Bilmes. 2013. Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints. Adv. in Neu. Inf. Proc. Sys. (NIPS) (2013)."},{"key":"e_1_3_2_2_36_1","volume-title":"Proc. Sys. (NIPS)","author":"Iyer Rishabh","year":"2013","unstructured":"Rishabh Iyer , Stefanie Jegelka , and Jeff A. Bilmes . 2013. Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions. Adv. in Neu. Inf . Proc. Sys. (NIPS) ( 2013 ). Rishabh Iyer, Stefanie Jegelka, and Jeff A. Bilmes. 2013. Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions. Adv. in Neu. Inf. Proc. Sys. (NIPS) (2013)."},{"key":"e_1_3_2_2_37_1","unstructured":"Stefanie Jegelka Francis Bach and Suvrit Sra. 2013.  Stefanie Jegelka Francis Bach and Suvrit Sra. 2013."},{"key":"e_1_3_2_2_38_1","volume-title":"Proc. Sys. (NIPS)","author":"Reflection","year":"2013","unstructured":"Reflection methods for user-friendly submodular optimization. Adv. in Neu. Inf . Proc. Sys. (NIPS) ( 2013 ). Reflection methods for user-friendly submodular optimization. Adv. in Neu. Inf. Proc. Sys. (NIPS) (2013)."},{"key":"e_1_3_2_2_39_1","unstructured":"Stefanie Jegelka and Jeff Bilmes. 2011.  Stefanie Jegelka and Jeff Bilmes. 2011."},{"key":"e_1_3_2_2_40_1","unstructured":"Online Submodular Minimization for Combinatorial Structures. In ICML. 345\u2013352.  Online Submodular Minimization for Combinatorial Structures. In ICML. 345\u2013352."},{"key":"e_1_3_2_2_41_1","volume-title":"Bilmes","author":"Jegelka Stefanie","year":"2011","unstructured":"Stefanie Jegelka , Hui Lin , and Jeff A . Bilmes . 2011 . On fast approximate submodular minimization. In NIPS. 460\u2013468. Stefanie Jegelka, Hui Lin, and Jeff A. Bilmes. 2011. On fast approximate submodular minimization. In NIPS. 460\u2013468."},{"key":"e_1_3_2_2_42_1","unstructured":"Alexander S Kelso  Jr and Vincent P Crawford. 1982.  Alexander S Kelso Jr and Vincent P Crawford. 1982."},{"key":"e_1_3_2_2_43_1","volume-title":"coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society","author":"Job","year":"1982","unstructured":"Job matching , coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society ( 1982 ), 1483\u20131504. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society (1982), 1483\u20131504."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.217"},{"key":"e_1_3_2_2_45_1","volume-title":"Torr","author":"Kohli Pushmeet","year":"2010","unstructured":"Pushmeet Kohli and Philip H. S . Torr . 2010 . Pushmeet Kohli and Philip H. S. Torr. 2010."},{"key":"e_1_3_2_2_46_1","unstructured":"Dynamic graph cuts and their applications in computer vision. Computer Vision: Detection Recognition and Reconstruction. (2010).  Dynamic graph cuts and their applications in computer vision. Computer Vision: Detection Recognition and Reconstruction. (2010)."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.025"},{"key":"e_1_3_2_2_48_1","unstructured":"S. Lacoste-Julien and M. Jaggi. 2015.  S. Lacoste-Julien and M. Jaggi. 2015."},{"key":"e_1_3_2_2_49_1","volume-title":"Proc. Sys. (NIPS).","author":"On","unstructured":"On the Global Linear Convergence of Frank-Wolfe Optimization Variants. In Adv. in Neu. Inf . Proc. Sys. (NIPS). On the Global Linear Convergence of Frank-Wolfe Optimization Variants. In Adv. in Neu. Inf. Proc. Sys. (NIPS)."},{"key":"e_1_3_2_2_50_1","unstructured":"Yin Tat Lee Aaron Sidford and Sam Chiu-Wai Wong. 2015.  Yin Tat Lee Aaron Sidford and Sam Chiu-Wai Wong. 2015."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_3_2_2_52_1","unstructured":"Hui Lin and Jeff Bilmes. 2010.  Hui Lin and Jeff Bilmes. 2010."},{"key":"e_1_3_2_2_53_1","volume-title":"NIPS workshop on Discrete Optimization in Machine Learning","author":"An","year":"2010","unstructured":"An application of the submodular principal partition to training data subset selection . NIPS workshop on Discrete Optimization in Machine Learning ( 2010 ). An application of the submodular principal partition to training data subset selection. NIPS workshop on Discrete Optimization in Machine Learning (2010)."},{"key":"e_1_3_2_2_54_1","volume-title":"Proc. Ann. Conf. Int. Speech Comm. Ass. (INTERSPEECH)","author":"Lin Hui","year":"2011","unstructured":"Hui Lin and Jeff Bilmes . 2011 . Optimal Selection of Limited Vocabulary Speech Corpora . Proc. Ann. Conf. Int. Speech Comm. Ass. (INTERSPEECH) (2011). Hui Lin and Jeff Bilmes. 2011. Optimal Selection of Limited Vocabulary Speech Corpora. Proc. Ann. Conf. Int. Speech Comm. Ass. (INTERSPEECH) (2011)."},{"key":"e_1_3_2_2_55_1","volume-title":"Submodular Functions and Convexity. Mathematical Programming \u2013 The State of the Art","author":"Lovasz Laszlo","year":"1983","unstructured":"Laszlo Lovasz . 1983. Submodular Functions and Convexity. Mathematical Programming \u2013 The State of the Art . A. Bachem, M. Grotschel, B. Korte eds.,Springer ( 1983 ), 235 \u2013 257. Laszlo Lovasz. 1983. Submodular Functions and Convexity. Mathematical Programming \u2013 The State of the Art. A. Bachem, M. Grotschel, B. Korte eds.,Springer (1983), 235 \u2013 257."},{"key":"e_1_3_2_2_56_1","volume-title":"the Handbook of Discrete Optimization","author":"McCormick S. T.","year":"2006","unstructured":"S. T. McCormick . 2006. Submodular Function Minimization . Chapter 7 in the Handbook of Discrete Optimization ( 2006 ). S. T. McCormick. 2006. Submodular Function Minimization. Chapter 7 in the Handbook of Discrete Optimization (2006)."},{"key":"e_1_3_2_2_57_1","volume-title":"Adrian Vladu, and Sam Chiu-Wai Wong.","author":"Mirrokni Vahab","year":"2015","unstructured":"Vahab Mirrokni , Renato Paes Leme , Adrian Vladu, and Sam Chiu-Wai Wong. December , 2015 . Vahab Mirrokni, Renato Paes Leme, Adrian Vladu, and Sam Chiu-Wai Wong. December, 2015."},{"key":"e_1_3_2_2_58_1","unstructured":"Tight Bounds for Approximate Caratheodory and Beyond. arXiv http:\/\/arxiv.org\/abs\/1512.08602 (December 2015).  Tight Bounds for Approximate Caratheodory and Beyond. arXiv http:\/\/arxiv.org\/abs\/1512.08602 (December 2015)."},{"key":"e_1_3_2_2_59_1","unstructured":"Yu Nesterov. 2003.  Yu Nesterov. 2003."},{"key":"e_1_3_2_2_60_1","volume-title":"A Basic Course","author":"Convex Optimization Introductory Lectures","year":"2008","unstructured":"Introductory Lectures on Convex Optimization : A Basic Course . Vol. I . http:\/\/enpub.fulton.asu.edu\/cseml\/Fall 2008 _ConvOpt\/book\/Intronl.pdf Introductory Lectures on Convex Optimization: A Basic Course. Vol. I. http:\/\/enpub.fulton.asu.edu\/cseml\/Fall2008_ConvOpt\/book\/Intronl.pdf"},{"key":"e_1_3_2_2_61_1","volume-title":"Proc. Sys. (NIPS)","author":"Nishihara Robert","year":"2014","unstructured":"Robert Nishihara , Stefanie Jegelka , and Michael I. Jordan . 2014. On the convergence rate of decomposable submodular function minimization. Adv. in Neu. Inf . Proc. Sys. (NIPS) ( 2014 ). Robert Nishihara, Stefanie Jegelka, and Michael I. Jordan. 2014. On the convergence rate of decomposable submodular function minimization. Adv. in Neu. Inf. Proc. Sys. (NIPS) (2014)."},{"key":"e_1_3_2_2_62_1","unstructured":"Adarsh Prasad Stefanie Jegelka and Dhruv Batra. 2014.  Adarsh Prasad Stefanie Jegelka and Dhruv Batra. 2014."},{"key":"e_1_3_2_2_63_1","volume-title":"Proc. Sys. (NIPS).","author":"Submodular","unstructured":"Submodular meets structured : Finding diverse subsets in exponentially-large structured item sets. In Adv. in Neu. Inf . Proc. Sys. (NIPS). Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets. In Adv. in Neu. Inf. Proc. Sys. (NIPS)."},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"e_1_3_2_2_65_1","volume-title":"Proc. Sys. (NIPS)","author":"Stobbe Peter","year":"2010","unstructured":"Peter Stobbe and Andreas Krause . 2010 . Efficient minimization of decomposable submodular functions. Adv. in Neu. Inf . Proc. Sys. (NIPS) (2010). Peter Stobbe and Andreas Krause. 2010. Efficient minimization of decomposable submodular functions. Adv. in Neu. Inf. Proc. Sys. (NIPS) (2010)."},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783352"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055419","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:27Z","timestamp":1750220607000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055419"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":65,"alternative-id":["10.1145\/3055399.3055419","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055419","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}