{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:46Z","timestamp":1725488626752},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441472"},{"type":"electronic","value":"9783540457268"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45726-7_2","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T05:55:49Z","timestamp":1186811749000},"page":"11-25","source":"Crossref","is-referenced-by-count":1,"title":["On Testing Convexity and Submodularity"],"prefix":"10.1007","author":[{"given":"Michal","family":"Parnas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,8,23]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"T. Batu, R. Rubinfeld, and P. White. Fast approximate pcps for multidimensional bin-packing problems. In Proceedings of RANDOM, pages 245\u2013256, 1999.","DOI":"10.1007\/978-3-540-48413-4_25"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"R.E. Burkard, B. Klinz, and R. Rudolf. Perspectives of monge properties in optimization. Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 70, 1996.","DOI":"10.1016\/0166-218X(95)00103-X"},{"key":"2_CR3","unstructured":"S. de Vries and R. Vohra. Combinatorial auctions: a survey. available from: http:\/\/www.kellogg.nwu.edu\/faculty\/vohra\/htm\/res.htm , 2000."},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnit-sky. Improved testing algorithms for monotonocity. In Proceedings of RANDOM, pages 97\u2013108, 1999.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"F. Ergun, S. Kannan, S. R. Kumar, R. Rubinfeld, and M. Viswanathan. Spot-checkers. In Proceedings of the Thirty-Second Annual ACM Symposium on the Theory of Computing, pages 259\u2013268, 1998.","DOI":"10.1145\/276698.276757"},{"key":"2_CR6","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"E. Fischer. The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science, 75:97\u2013126, 2001.","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Sam-rodnitsky. Monotonicity testing over general poset domains. In Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing, 2002.","DOI":"10.1145\/509907.509977"},{"issue":"3","key":"2_CR8","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. Testing monotonicity. Combinatorica, 20(3):301\u2013337, 2000.","journal-title":"Combinatorica"},{"issue":"4","key":"2_CR9","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. JACM, 45(4):653\u2013750, 1998.","journal-title":"JACM"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"M. Grotschel, L. Lovasz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 1981.","DOI":"10.1007\/BF02579273"},{"key":"2_CR11","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1090\/pspum\/007\/0157778","volume":"7","author":"A.J. Hoffman","year":"1963","unstructured":"A.J. Hoffman. On simple linear programming problems. In In Proceedings of Symposia in Pure Mathematics, Convexity, volume 7, pages 317\u2013327, 1963. American Mathematical Society.","journal-title":"In Proceedings of Symposia in Pure Mathematics, Convexity"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"S. Iwata, L. Fleischer, and S. Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. In Proceedings of the Thirty-Fourth Annual ACM Symposium on the Theory of Computing, pages 96\u2013107, 2000. To appear in JACM.","DOI":"10.1145\/335305.335317"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"B. Lehmann, D. Lehmann, and N. Nisan. Combinatorial auctions with decreasing marginal utilities. In ACM Conference on Electronic Commerce, pages-, 2001.","DOI":"10.1145\/501158.501161"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz. Submodular functions and convexity. Mathematical Programming: The State of the Art, pages 235\u2013257, 1983.","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"M. Parnas, D. Ron, and R. Rubinfeld. On testing convexity and submodularity. Available from: http:\/\/www.eng.tau.ac.il\/~danar\/papers.html , 2002.","DOI":"10.1007\/3-540-45726-7_2"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"D. Ron. Property testing. In Handbook on Randomization, Volume II, pages 597\u2013649, 2001.","DOI":"10.1007\/978-1-4615-0013-1_15"},{"issue":"2","key":"2_CR17","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252\u2013271, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"A. Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory B, 80:346\u2013355, 2000.","journal-title":"Journal of Combinatorial Theory B"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45726-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T19:04:49Z","timestamp":1556737489000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45726-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441472","9783540457268"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-45726-7_2","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}