{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T16:31:18Z","timestamp":1792168278654,"version":"4.4.0"},"reference-count":98,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-09-1-0538"],"award-info":[{"award-number":["FA9550-09-1-0538"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-09-1-0751"],"award-info":[{"award-number":["N00014-09-1-0751"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0953192"],"award-info":[{"award-number":["CCF-0953192"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1101283"],"award-info":[{"award-number":["CCF-1101283"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications. They have been used in many areas, including combinatorial optimization, machine learning, and economics. In this work we study submodular functions from a learning theoretic angle. We provide algorithms for learning submodular functions, as well as lower bounds on their learnability. In doing so, we uncover several novel structural results revealing ways in which submodular functions can be both surprisingly structured and surprisingly unstructured. We provide several concrete implications of our work in other domains including algorithmic game theory and combinatorial optimization. At a technical level, this research combines ideas from many areas, including learning theory (distributional learning and PAC-style analyses), combinatorics and optimization (matroids and submodular functions), and pseudorandomness (lossless expander graphs).<\/jats:p>","DOI":"10.1137\/120888909","type":"journal-article","created":{"date-parts":[[2018,5,31]],"date-time":"2018-05-31T10:13:47Z","timestamp":1527761627000},"page":"703-754","source":"Crossref","is-referenced-by-count":8,"title":["Submodular Functions: Learnability, Structure, and Optimization"],"prefix":"10.1137","volume":"47","author":[{"given":"Maria-Florina","family":"Balcan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicholas J. A.","family":"Harvey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,5,31]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , Wiley, New York, 2000.","DOI":"10.1002\/0471722154"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. Anthony and P. Bartlett,\n                      Neural Network Learning: Theoretical Foundations\n                      , Cambridge University Press, Cambridge, UK, 1999.","DOI":"10.1017\/CBO9780511624216"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg, N. Nisan, and T. Roughgarden,\n                      Sketching valuation functions\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2012.","DOI":"10.1137\/1.9781611973099.81"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"M. F. Balcan, A. Blum, and Y. Mansour,\n                      Item pricing for revenue maxmimization\n                      , in Proceedings of the ACM Conference on Electronic Commerce, 2009.","DOI":"10.1145\/1386790.1386802"},{"key":"atypb5","unstructured":"M.F. Balcan, F. Constantin, S. Iwata, and L. Wang,\n                      Learning valuation functions\n                      , in Proceedings of the 25th Conference on Learning Theory, 2012."},{"key":"atypb6","unstructured":"M. F. Balcan, E. Vitercik, and C. White,\n                      Learning combinatorial functions from pairwise comparisons\n                      , in Proceedings of the 29th Conference on Learning Theory, 2016."},{"key":"atypb7","unstructured":"E. Baum and K. Lang,\n                      Query learning can work poorly when a human oracle is used\n                      , in Proceedings of the IEEE International Joint Conference on Neural Networks, 1993."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Bing, D. Lehmann, and P. Milgrom,\n                      Presentation and structure of substitutes valuations\n                      , in Proceedings of the ACM Conference on Electronic Commerce, 2004.","DOI":"10.1145\/988772.988812"},{"key":"atypb9","unstructured":"L. Blumrosen,\n                      Information and Communication in Mechanism Design\n                      , Ph.D. thesis, Hebrew University, Jerusalem, 2006."},{"key":"atypb10","first-page":"29","author":"Blumrosen L.","year":"2005","journal-title":"Proceedings of the ACM Conference on Electronic Commerce"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v14-690"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405292"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"atypb14","unstructured":"C. Chekuri and J. Vondr\u00e1k,\n                      Randomized Pipage Rounding for Matroid Polytopes and Applications\n                      ,arXiv:0909.4348v1, 2009."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"C. Chekuri, J. Vondr\u00e1k, and R. Zenklusen,\n                      Dependent randomized rounding via exchange properties of combinatorial structures\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 575-584.","DOI":"10.1109\/FOCS.2010.60"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"C. Chekuri, J. Vondrak, and R. Zenklusen,\n                      Submodular function maximization via the multilinear relaxation and contention resolution schemes\n                      , in Proceedings of the ACM Symposium on Theory of Computing, 2011.","DOI":"10.1145\/1993636.1993740"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Cheraghchi, A. R. Klivans, P. Kothari, and H. K. Lee,\n                      Submodular functions are noise stable\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2012.","DOI":"10.1137\/1.9781611973099.126"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"P. Cramton, Y. Shoham, and R. Steinberg, eds.\n                      Combinatorial Auctions\n                      , MIT Press, Cambridge, MA, 2006.","DOI":"10.7551\/mitpress\/9780262033428.001.0001"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"L. Devroye, L. Gy\u00f6rfi, and G. Lugosi,\n                      A Probabilistic Theory of Pattern Recognition\n                      , Springer, New York, 1996.","DOI":"10.1007\/978-1-4612-0711-5"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"S. Dobzinski, N. Nisan, and M. Schapira,\n                      Truthful randomized mechanisms for combinatorial auctions\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 644-652.","DOI":"10.1145\/1132516.1132607"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Dobzinski and J. Vondr\u00e1k,\n                      Communication complexity of combinatorial auctions with submodular valuations\n                      , in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, pp. 1205-1215.","DOI":"10.1137\/1.9781611973105.87"},{"key":"atypb22","first-page":"69","author":"Edmonds J.","year":"1970","journal-title":"New York"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00202-2"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"U. Feige, V. Mirrokni, and J. Vondr\u00e1k,\n                      Maximizing non-monotone submodular functions\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007.","DOI":"10.1109\/FOCS.2007.4389516"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"M. Feldman, J. Naor, and R. Schwartz,\n                      Nonmonotone submodular maximization via a structural continuous greedy algorithm\n                      , in Proceedings of the 38th International Colloquium on Automata, Languages and Programming, 2011.","DOI":"10.1007\/978-3-642-22006-7_29"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"M. Feldman, J. Naor, and R. Schwartz,\n                      A unified continuous greedy algorithm for submodular maximization\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, 2011.","DOI":"10.1109\/FOCS.2011.46"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"V. Feldman and J. Vondr\u00e1k,\n                      Tight bounds on low-degree spectral concentration of submodular and XOS functions\n                      , in Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, 2015.","DOI":"10.1109\/FOCS.2015.61"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/140958207"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"Y. Filmus and J. Ward,\n                      A tight combinatorial algorithm for submodular maximization subject to a matroid constraint\n                      , in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012, pp. 659-668.","DOI":"10.1109\/FOCS.2012.55"},{"key":"atypb30","unstructured":"A. Frank,\n                      Connections in Combinatorial Optimization\n                      , Oxford University Press, New York, 2011."},{"key":"atypb31","unstructured":"S. Fujishige,\n                      Submodular Functions and Optimization\n                      , Elsevier, Amsterdam, 2005."},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"G. Goel, C. Karande, P. Tripathi, and L. Wang,\n                      Approximability of combinatorial problems with multi-agent submodular cost functions\n                      , in Proceedings of the 50th Annual Symposium on Foundations of Computer Science, 2009.","DOI":"10.1109\/FOCS.2009.81"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"M. Goemans, N. Harvey, S. Iwata, and V. Mirrokni,\n                      Approximating submodular functions everywhere\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2009.","DOI":"10.1137\/1.9781611973068.59"},{"key":"atypb34","unstructured":"M. Goemans, R. Kleinberg, N. Harvey, and V. Mirrokni,\n                      On Learning Submodular Functions\n                      , manuscript, 2008."},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer, New York, 1993.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"A. Gupta, M. Hardt, A. Roth, and J. Ullman,\n                      Privately releasing conjunctions and the statistical query barrier\n                      , in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 2011.","DOI":"10.1145\/1993636.1993742"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"V. Guruswami and P. Raghavendra,\n                      Hardness of learning halfspaces with noise\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006.","DOI":"10.1109\/FOCS.2006.33"},{"key":"atypb39","first-page":"56","author":"Guruswami V.","year":"2009","journal-title":"J. ACM"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"M. T. Hajiaghayi, J. H. Kim, T. Leighton, and H. R\u00e4cke,\n                      Oblivious routing in directed graphs with random demands\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 193-201.","DOI":"10.1145\/1060590.1060619"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.36.2.155"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"T. Hastie, R. Tibshirani, and J. Friedman,\n                      The Elements of Statistical Learning: Data Mining, Inference, and Prediction\n                      , Springer, New York, 2009.","DOI":"10.1007\/978-0-387-84858-7"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"S. Iwata and K. Nagano,\n                      Submodular function minimization under covering constraints\n                      , in Proceedings of the 50th Annual Symposium on Foundations of Computer Science, 2009.","DOI":"10.1109\/FOCS.2009.31"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"S. Iwata and J. Orlin,\n                      A simple combinatorial algorithm for submodular function minimization\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2009.","DOI":"10.1137\/1.9781611973068.133"},{"key":"atypb48","unstructured":"R. K. Iyer, S. Jegelka, and J. A. Bilmes,\n                      Curvature and optimal algorithms for learning and minimizing submodular functions\n                      , in 27th Annual Conference on Neural Information Processing Systems, 2013."},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Ruci\u0144ski,\n                      Random Graphs\n                      , Wiley-Interscience, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb50","unstructured":"S. Jegelka and J. Bilmes,\n                      Notes on graph cuts with submodular edge weights\n                      , in Proceedings of the Workshop on Discrete Optimization in Machine Learning: Submodularity, Sparsity & Polyhedra, 2009."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/0211014"},{"key":"atypb52","first-page":"187","author":"John F.","year":"1948","journal-title":"New York"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"A. T. Kalai, A. Samorodnitsky, and S. Teng,\n                      Learning and smoothed analysis\n                      , in Proceedings of the 50th Annual Symposium on Foundations of Computer Science, 2009.","DOI":"10.1109\/FOCS.2009.60"},{"key":"atypb55","unstructured":"G. Kalai,\n                      Learnability and Rationality of Choice\n                      , Technical report, Institute of Mathematics and Center for Rationality, Hebrew University of Jerusalem, Jerusalem, Israel, 2001."},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0531(03)00083-8"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174647"},{"key":"atypb58","doi-asserted-by":"crossref","unstructured":"M. Kearns and U. Vazirani,\n                      An Introduction to Computational Learning Theory\n                      , MIT Press, Cambridge, MA, 1994.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.2307\/1913392"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"atypb61","unstructured":"A. Krause and C. Guestrin,\n                      Near-optimal nonmyopic value of information in graphical models\n                      , in Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, 2005."},{"key":"atypb62","unstructured":"A. Krause and C. Guestrin,\n                      Beyond Convexity: Submodularity in Machine Learning\n                      , 2008,http:\/\/www.select.cs.cmu.edu\/tutorials\/icml08submodularity.html."},{"key":"atypb63","unstructured":"A. Krause and C. Guestrin,\n                      Intelligent Information Gathering and Submodular Function Optimization\n                      ,http:\/\/www.ijcai.org\/past\/ijcai-09\/tutorials\/tutorial-MP4.html(2009)."},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.60"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0463"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"atypb70","first-page":"235","author":"Lov\u00e1sz L.","year":"1983","journal-title":"New York"},{"key":"atypb71","first-page":"321","author":"McCormick S. T.","year":"2006","journal-title":"Amsterdam"},{"key":"atypb72","doi-asserted-by":"publisher","DOI":"10.1086\/262118"},{"key":"atypb73","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal,\n                      Probability and Computing: Randomized Algorithms and Probabilistic Analysis\n                      , Cambridge University Press, Cambridge, UK, 2005.","DOI":"10.1017\/CBO9780511813603"},{"key":"atypb74","doi-asserted-by":"crossref","unstructured":"M. Molloy and B. Reed,\n                      Graph Colouring and the Probabilistic Method\n                      , Springer, New York, 2001.","DOI":"10.1007\/978-3-642-04016-0"},{"key":"atypb75","doi-asserted-by":"crossref","unstructured":"K. Murota,\n                      Discrete Convex Analysis\n                      , Discrete Math. Appl., SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718508"},{"key":"atypb76","unstructured":"M. Narasimhan and J. Bilmes,\n                      Local search for balanced submodular clusterings\n                      , in Proceedings of the 20th International Joint Conference on Artificial Intelligence, 2007."},{"key":"atypb77","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"atypb78","unstructured":"Proceedings of the\n                      NIPS Workshop on Discrete Optimization in Machine Learning (DISCML): Submodularity, Sparsity $\\&$ Polyhedra\n                      ,http:\/\/www.discml.cc(2009)."},{"key":"atypb79","unstructured":"Proceedings of the\n                      NIPS Workshop on Discrete Optimization in Machine Learning (DISCML): Uncertainty, Generalization and Feedback\n                      ,http:\/\/las.ethz.ch\/discml(2011)."},{"key":"atypb80","doi-asserted-by":"crossref","unstructured":"N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, eds.\n                      Algorithmic Game Theory\n                      , Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511800481"},{"key":"atypb81","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.83"},{"key":"atypb82","unstructured":"J. G. Oxley,\n                      Matroid Theory\n                      , Oxford University Press, New York, 1992."},{"key":"atypb83","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120902"},{"key":"atypb84","doi-asserted-by":"crossref","unstructured":"S. Raskhodnikova and G. Yaroslavtsev,\n                      Learning Pseudo-Boolean $k$-$DNF$ and Submodular Functions\n                      ,arXiv:1208.2294, 2012.","DOI":"10.1137\/1.9781611973105.98"},{"key":"atypb85","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"atypb86","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency\n                      , Springer, New York, 2004."},{"key":"atypb87","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.003"},{"key":"atypb88","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"key":"atypb89","doi-asserted-by":"crossref","unstructured":"Z. Svitkina and L. Fleischer,\n                      Submodular approximation: Sampling-based algorithms and lower bounds\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008.","DOI":"10.1109\/FOCS.2008.66"},{"key":"atypb90","doi-asserted-by":"publisher","DOI":"10.1007\/BF02699376"},{"key":"atypb91","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"atypb92","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"atypb93","unstructured":"V. N. Vapnik,\n                      Statistical Learning Theory\n                      , Wiley, New York, 1998."},{"key":"atypb94","unstructured":"S. A. Vinterbo,\n                      A stab at approximating minimum subadditive join\n                      , in Proceedings of the 10th International Workshop on Algorithms and Data Structures, 2007."},{"key":"atypb95","doi-asserted-by":"crossref","unstructured":"J. Vondr\u00e1k,\n                      Optimal approximation for the submodular welfare problem in the value oracle model\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008.","DOI":"10.1145\/1374376.1374389"},{"key":"atypb96","first-page":"651","author":"Vondr\u00e1k J.","year":"2009","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"key":"atypb97","unstructured":"J. Vondr\u00e1k,\n                      A Note on Concentration of Submodular Functions\n                      ,arXiv:1005.2791, 2010."},{"key":"atypb98","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120888909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:41:22Z","timestamp":1787337682000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120888909"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":98,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/120888909"],"URL":"https:\/\/doi.org\/10.1137\/120888909","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}