{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:21:42Z","timestamp":1725488502536},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424239"},{"type":"electronic","value":"9783540446347"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44634-6_4","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:20:48Z","timestamp":1186741248000},"page":"26-37","source":"Crossref","is-referenced-by-count":3,"title":["Using the Pseudo-Dimension to Analyze Approximation Algorithms for Integer Programming"],"prefix":"10.1007","author":[{"given":"Philip M.","family":"Long","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"M. Anthony and P. L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.","DOI":"10.1017\/CBO9780511624216"},{"issue":"4","key":"4_CR2","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1145\/263867.263927","volume":"44","author":"N. Alon","year":"1997","unstructured":"N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the Association for Computing Machinery, 44(4):616\u2013631, 1997.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the Association for Computing Machinery, 41:153\u2013180, 1994.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"4_CR4","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1006\/jcss.1995.1008","volume":"50","author":"S. Ben-David","year":"1992","unstructured":"S. Ben-David, N. Cesa-Bianchi, D. Haussler, and P. M. Long. Characterizations of learnability for classes of 0,..., n-valued functions. Journal of Computer and System Sciences, 50(1):74\u201386, 1992.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"4_CR5","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. JACM, 36(4):929\u2013965, 1989.","journal-title":"JACM"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Bronnimann","year":"1995","unstructured":"H. Bronnimann and M. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom., 14:263\u2013279, 1995.","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jcss.1997.1557","volume":"56","author":"P. L. Bartlett","year":"1998","unstructured":"P. L. Bartlett and P. M. Long. Prediction, learning, uniform convergence, and scale-sensitive dimensions. Journal of Computer and System Sciences, 56(2):174\u2013190, 1998.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"4_CR8","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1006\/jcss.1996.0033","volume":"52","author":"P. L. Bartlett","year":"1996","unstructured":"P. L. Bartlett, P. M. Long, and R. C. Williamson. Fat-shattering and the learnability of real-valued functions. Journal of Computer and System Sciences, 52(3):434\u2013452, 1996.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR9","unstructured":"P. Crescenzi and V. Kann. A compendium of NP optimization problems. See \n                    http:\/\/www.nada.kth.se\/viggo\/problemlist\/compendium.html\n                    \n                  ."},{"issue":"6","key":"4_CR10","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1214\/aop\/1176995384","volume":"6","author":"R. M. Dudley","year":"1978","unstructured":"R. M. Dudley. Central limit theorems for empirical measures. Annals of Probability, 6(6):899\u2013929, 1978.","journal-title":"Annals of Probability"},{"key":"4_CR11","first-page":"1","volume":"89","author":"M.R. Fellows","year":"1987","unstructured":"M.R. Fellows. The Robertson-Seymour theorems: A survey of applications. Contemp. Math., 89:1\u201318, 1987.","journal-title":"Contemp. Math."},{"issue":"2","key":"4_CR12","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1006\/inco.1995.1136","volume":"121","author":"Y. Freund","year":"1995","unstructured":"Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256\u2013285, 1995.","journal-title":"Information and Computation"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1006\/jcss.1997.1504","volume":"55","author":"Y. Freund","year":"1997","unstructured":"Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119\u2013139, 1997.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","volume":"100","author":"D. Haussler","year":"1992","unstructured":"D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78\u2013150, 1992.","journal-title":"Information and Computation"},{"issue":"2","key":"4_CR15","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0097-3165(95)90052-7","volume":"69","author":"D. Haussler","year":"1995","unstructured":"D. Haussler. Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217\u2013232, 1995.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","volume":"46","author":"A. Hajnal","year":"1993","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy, and G. Tur\u00e1n. Threshold circuits of bounded depth. Journal of Computer and System Sciences, 46:129\u2013154, 1993.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"4_CR17","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/S0022-0000(05)80062-5","volume":"48","author":"M. J. Kearns","year":"1994","unstructured":"M. J. Kearns and R. E. Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464\u2013497, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"4_CR18","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1006\/inco.1994.1100","volume":"115","author":"P.G. Kolaitis","year":"1994","unstructured":"P.G. Kolaitis and M.N. Thakur. Logical definability of NP optimization problems. Information and Computation, 115(2):321\u2013353, 1994.","journal-title":"Information and Computation"},{"key":"4_CR19","unstructured":"Y. Li, P. M. Long, and A. Srinivasan. Improved bounds on the sample complexity of learning. Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 309\u2013318, 2000."},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383\u2013390, 1975.","journal-title":"Discrete Mathematics"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"4_CR22","first-page":"67","volume":"4","author":"B. K. Natarajan","year":"1989","unstructured":"B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67\u201397, 1989.","journal-title":"Machine Learning"},{"issue":"1","key":"4_CR23","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1137\/S0097539792237462","volume":"24","author":"M. Naor","year":"1995","unstructured":"M. Naor and R. M. Roth. Optimal file sharing in distributed networks. SIAM J. Comput., 24(1):158\u2013183, 1995.","journal-title":"SIAM J. Comput."},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"J. Pach and P.K. Agarwal. Combinatorial Geometry. John Wiley and Sons, 1995.","DOI":"10.1002\/9781118033203"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"D. Pollard. Convergence of Stochastic Processes. Springer Verlag, 1984.","DOI":"10.1007\/978-1-4612-5254-2"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"J.R. Quinlan. Some elements of machine learning. Proceedings of the Sixteenth International Conference on Machine Learning, pages 523\u2013524, 1999.","DOI":"10.1007\/3-540-48751-4_3"},{"key":"4_CR27","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences, 37:130\u2013143, 1988.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"4_CR28","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","volume":"30","author":"F.P. Ramsey","year":"1930","unstructured":"F.P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematics Society, 30(2):264\u2013286, 1930.","journal-title":"Proceedings of the London Mathematics Society"},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"S. Roy. Semantic complexity of relational queries and data independent data partitioning. Proceedings of the ACM SIGACT-SIGART-SIGMOD Annual Symposium on Principles of Database Systems, 1991.","DOI":"10.1145\/113413.113437"},{"issue":"4","key":"4_CR30","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0166-218X(93)90179-R","volume":"42","author":"J. Shawe-Taylor","year":"1993","unstructured":"J. Shawe-Taylor, M. Anthony, and N. Biggs. Bounding the sample size with the Vapnik-Chervonenkis dimension. Discrete Applied Mathematics, 42:65\u201373, 1993.","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR32","first-page":"197","volume":"5","author":"R. Schapire","year":"1990","unstructured":"R. Schapire. The strength of weak learnability. Machine Learning, 5:197\u2013227, 1990.","journal-title":"Machine Learning"},{"issue":"5","key":"4_CR33","doi-asserted-by":"publisher","first-page":"1651","DOI":"10.1214\/aos\/1024691352","volume":"26","author":"R. E. Schapire","year":"1998","unstructured":"Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651\u20131686, 1998.","journal-title":"The Annals of Statistics"},{"key":"4_CR34","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A. Srinivasan","year":"1999","unstructured":"A. Srinivasan. Improved approximation guarantees for packing and covering integer programs. SIAM Journal on Computing, 29:648\u2013670, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR35","unstructured":"A. Srinivasan. New approaches to covering and packing problems. Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001."},{"key":"4_CR36","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1214\/aop\/1176988847","volume":"22","author":"M. Talagrand","year":"1994","unstructured":"M. Talagrand. Sharper bounds for Gaussian and empirical processes. Annals of Probability, 22:28\u201376, 1994.","journal-title":"Annals of Probability"},{"issue":"11","key":"4_CR37","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134\u20131142, 1984.","journal-title":"Communications of the ACM"},{"key":"4_CR38","unstructured":"V. N. Vapnik. Estimation of Dependencies based on Empirical Data. Springer Verlag, 1982."},{"key":"4_CR39","doi-asserted-by":"crossref","unstructured":"V. N. Vapnik. Inductive principles of the search for empirical dependences (methods based on weak convergence of probability measures). Proceedings of the 1989 Workshop on Computational Learning Theory, 1989.","DOI":"10.1016\/B978-0-08-094829-4.50004-0"},{"issue":"2","key":"4_CR40","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264\u2013280, 1971.","journal-title":"Theory of Probability and its Applications"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44634-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T06:39:33Z","timestamp":1550731173000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44634-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424239","9783540446347"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-44634-6_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}