{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T06:38:58Z","timestamp":1784097538494,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T00:00:00Z","timestamp":1307318400000},"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":[[2011,6,6]]},"DOI":"10.1145\/1993636.1993741","type":"proceedings-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:53:52Z","timestamp":1307361232000},"page":"793-802","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Learning submodular functions"],"prefix":"10.1145","author":[{"given":"Maria-Florina","family":"Balcan","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicholas J.A.","family":"Harvey","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,6,6]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Submodularity, sparsity & polyhedra (DISCML)","author":"NIPS","year":"2009","unstructured":"NIPS workshop on discrete optimization in machine learning : Submodularity, sparsity & polyhedra (DISCML) , 2009 . http:\/\/www.discml.cc\/. NIPS workshop on discrete optimization in machine learning: Submodularity, sparsity & polyhedra (DISCML), 2009. http:\/\/www.discml.cc\/."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.012"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/554131"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.45.12.1613"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386802"},{"key":"e_1_3_2_2_7_1","volume-title":"August","author":"Balcan M.-F.","year":"2010","unstructured":"M.-F. Balcan and Nicholas J. A. Harvey . Learning submodular functions , August 2010 . arXiv:1008.2159. M.-F. Balcan and Nicholas J. A. Harvey. Learning submodular functions, August 2010. arXiv:1008.2159."},{"key":"e_1_3_2_2_8_1","volume-title":"IJCNN","author":"Baum E.","year":"1993","unstructured":"E. Baum and K. Lang . Query learning can work poorly when a human oracle is used . In IJCNN , 1993 . E. Baum and K. Lang. Query learning can work poorly when a human oracle is used. In IJCNN, 1993."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796412"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v14-690"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234564"},{"key":"e_1_3_2_2_12_1","volume-title":"September","author":"Chekuri C.","year":"2009","unstructured":"C. Chekuri and J. Vondr\u00e1k . Randomized pipage rounding for matroid polytopes and applications , September 2009 . arXiv:0909.4348v1. C. Chekuri and J. Vondr\u00e1k. Randomized pipage rounding for matroid polytopes and applications, September 2009. arXiv:0909.4348v1."},{"key":"e_1_3_2_2_13_1","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"Edmonds J.","year":"1970","unstructured":"J. Edmonds . Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Sch\u00f6nheim, editors , Combinatorial Structures and Their Applications , pages 69 -- 87 . Gordon and Breach , 1970 . J. Edmonds. Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Sch\u00f6nheim, editors, Combinatorial Structures and Their Applications, pages 69--87. Gordon and Breach, 1970."},{"key":"e_1_3_2_2_14_1","volume-title":"Submodular Functions and Optimization","author":"Fujishige S.","year":"2005","unstructured":"S. Fujishige . Submodular Functions and Optimization . Elsevier , 2005 . S. Fujishige. Submodular Functions and Optimization. Elsevier, 2005."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496829"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060619"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.36.2.155"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The Elements of Statistical Learning: Data Mining, Inference, and Prediction","author":"Hastie T.","year":"2009","unstructured":"T. Hastie , R. Tibshirani , and J. Friedman . The Elements of Statistical Learning: Data Mining, Inference, and Prediction . Springer , 2009 . T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2009."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"Janson S.","year":"2000","unstructured":"S. Janson , T. \u0141uczak , and A. Ruci'nski . Random Graphs . Wiley-Interscience , 2000 . S. Janson, T. \u0141uczak, and A. Ruci'nski. Random Graphs. Wiley-Interscience, 2000."},{"key":"e_1_3_2_2_22_1","volume-title":"Studies and Essays, presented to R. Courant on his 60th Birthday","author":"John F.","year":"1948","unstructured":"F. John . Extremum problems with inequalities as subsidiary conditions . In Studies and Essays, presented to R. Courant on his 60th Birthday , January 8, 1948 , 1948. F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays, presented to R. Courant on his 60th Birthday, January 8, 1948, 1948."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/200548"},{"key":"e_1_3_2_2_24_1","volume-title":"UAI","author":"Krause A.","year":"2005","unstructured":"A. Krause and C. Guestrin . Near-optimal nonmyopic value of information in graphical models . In UAI , 2005 . A. Krause and C. Guestrin. Near-optimal nonmyopic value of information in graphical models. In UAI, 2005."},{"key":"e_1_3_2_2_25_1","volume-title":"Intelligent information gathering and submodular function optimization","author":"Krause A.","year":"2009","unstructured":"A. Krause and C. Guestrin . Intelligent information gathering and submodular function optimization , 2009 . http:\/\/submodularity.org\/ijcai09\/index.html. A. Krause and C. Guestrin. Intelligent information gathering and submodular function optimization, 2009. http:\/\/submodularity.org\/ijcai09\/index.html."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"e_1_3_2_2_28_1","volume-title":"Graph Colouring and the Probabilistic Method","author":"Molloy M.","year":"2001","unstructured":"M. Molloy and B. Reed . Graph Colouring and the Probabilistic Method . Springer , 2001 . M. Molloy and B. Reed. Graph Colouring and the Probabilistic Method. Springer, 2001."},{"key":"e_1_3_2_2_29_1","volume-title":"IJCAI","author":"Narasimhan M.","year":"2007","unstructured":"M. Narasimhan and J. Bilmes . Local search for balanced submodular clusterings . In IJCAI , 2007 . M. Narasimhan and J. Bilmes. Local search for balanced submodular clusterings. In IJCAI, 2007."},{"key":"e_1_3_2_2_30_1","volume-title":"Matroid Theory","author":"Oxley J. G.","year":"1992","unstructured":"J. G. Oxley . Matroid Theory . Oxford University Press , 1992 . J. G. Oxley. Matroid Theory. Oxford University Press, 1992."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1050.0252"},{"key":"e_1_3_2_2_32_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2004","unstructured":"A. Schrijver . Combinatorial Optimization: Polyhedra and Efficiency . Springer , 2004 . A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2004."},{"key":"e_1_3_2_2_33_1","volume-title":"ICS","author":"Seshadhri C.","year":"2011","unstructured":"C. Seshadhri and J. Vondr\u00e1k . Is submodularity testable ? In ICS , 2011 . C. Seshadhri and J. Vondr\u00e1k. Is submodularity testable? In ICS, 2011."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.66"},{"key":"e_1_3_2_2_35_1","volume-title":"Princeton University Press","author":"Topkis D. M.","year":"1998","unstructured":"D. M. Topkis . Supermodularity and Complementarity . Princeton University Press , 1998 . D. M. Topkis. Supermodularity and Complementarity. Princeton University Press, 1998."},{"key":"e_1_3_2_2_36_1","unstructured":"S. P. Vadhan. Pseudorandomness I. Foundations and Trends in Theoretical Computer Science. To Appear.   S. P. Vadhan. Pseudorandomness I. Foundations and Trends in Theoretical Computer Science. To Appear."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_2_38_1","volume-title":"Wiley and Sons","author":"Vapnik V. N.","year":"1998","unstructured":"V. N. Vapnik . Statistical Learning Theory . Wiley and Sons , 1998 . V. N. Vapnik. Statistical Learning Theory. Wiley and Sons, 1998."},{"key":"e_1_3_2_2_39_1","unstructured":"J. Vondr\u00e1k. A note on concentration of submodular functions May 2010. arXiv:1005.2791.  J. Vondr\u00e1k. A note on concentration of submodular functions May 2010. arXiv:1005.2791."},{"key":"e_1_3_2_2_40_1","volume-title":"Nonlinear Pricing","author":"Wilson R. B.","year":"1997","unstructured":"R. B. Wilson . Nonlinear Pricing . Oxford University Press , 1997 . R. B. Wilson. Nonlinear Pricing. Oxford University Press, 1997."}],"event":{"name":"STOC'11: Symposium on Theory of Computing","location":"San Jose California USA","acronym":"STOC'11","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-third annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993741","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993636.1993741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:11Z","timestamp":1750244771000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,6]]},"references-count":40,"alternative-id":["10.1145\/1993636.1993741","10.1145\/1993636"],"URL":"https:\/\/doi.org\/10.1145\/1993636.1993741","relation":{},"subject":[],"published":{"date-parts":[[2011,6,6]]},"assertion":[{"value":"2011-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}