{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:24:30Z","timestamp":1725665070375},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_13","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:22:18Z","timestamp":1330280538000},"page":"151-164","source":"Crossref","is-referenced-by-count":1,"title":["Probabilistic approximation of some NP optimization problems by finite-state machines"],"prefix":"10.1007","author":[{"given":"Dawei","family":"Hong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Camille","family":"Birget","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"13_CR1","first-page":"357","volume":"3","author":"K. Azuma","year":"1965","unstructured":"K. Azuma, Weighted sums of certain dependent variables, Tohoku Mathematical Journal 3 (1965) 357\u2013367.","journal-title":"Tohoku Mathematical Journal"},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"P. Crescenzi and A. Panconesi, Completeness in approximation classes, Information and Computation 93 (1991) 241\u2013262.","journal-title":"Information and Computation"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"E. G. Coffman, Jr., M. R. Garey, and D.S. Johnson, Approximation algorithms for bin packing \u2014 an updated survey. In G. Ausiello, M. Lucertini, and P. Serafini, editors,Algorithm Design for Computer System Design, CISM Courses and Lectures no. 284, pp. 49\u2013106, Springer-Verlag 1984.","DOI":"10.1007\/978-3-7091-4338-4_3"},{"key":"13_CR4","unstructured":"E. G. Coffman, Jr. and G.S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, John Wiley & Sons, 1991."},{"key":"13_CR5","volume-title":"Lecture Note \u2014 Monograph Series, Vol. 3","author":"P. Gaenssler","year":"1983","unstructured":"P. Gaenssler, Empirical Processes, Lecture Note \u2014 Monograph Series, Vol. 3, Institute of Mathematical Statistics, Hayward, CA, 1983."},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"S. Han, D. Hong and J. Y-T. Leung, Probabilistic analysis of a bin covering algorithm, Operations Research Letters Vol. 18 No. 4 (1995).","DOI":"10.1016\/0167-6377(95)00053-4"},{"key":"13_CR7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1965","unstructured":"W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, 58 (1965) 13\u201330.","journal-title":"Journal of the American Statistical Association"},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0020-0190(95)00044-D","volume":"55","author":"D. Hong","year":"1995","unstructured":"D. Hong and J. Y-T. Leung, Probabilistic analysis of k-dimensional packing algorithms, Information Processing Letters 55 (1995) 17\u201324.","journal-title":"Information Processing Letters"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences 9 (1974) 256\u2013278.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR10","first-page":"168","volume":"539","author":"J. F. C. Kingman","year":"1976","unstructured":"J. F. C. Kingman, Subadditive processes, Lecture Notes in Mathematics 539, pp. 168\u2013222, Springer-Verlag, 1976.","journal-title":"Lecture Notes in Mathematics"},{"key":"13_CR11","unstructured":"C. H. Papadimitriou, Computational Complexity, Addison \u2014 Wesley, 1994."}],"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-63248-4_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:43:20Z","timestamp":1619559800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}