{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:50:49Z","timestamp":1757314249256},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642296994"},{"type":"electronic","value":"9783642297007"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29700-7_16","type":"book-chapter","created":{"date-parts":[[2012,4,28]],"date-time":"2012-04-28T12:25:56Z","timestamp":1335615956000},"page":"172-181","source":"Crossref","is-referenced-by-count":4,"title":["A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing"],"prefix":"10.1007","author":[{"given":"Richard","family":"Beigel","sequence":"first","affiliation":[]},{"given":"Bin","family":"Fu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proceedings of the Symposium on Theory of Computing, pp. 20\u201329 (1996)","DOI":"10.1145\/237814.237823"},{"key":"16_CR2","unstructured":"Applegate, D., Buriol, L., Dillard, B., Johnson, D., Shore, P.: The cutting-stock approach to bin packing: Theory and experiments. In: Proceedings of Algorithm Engineering and Experimentation (ALENEX), pp. 1\u201315 (2003)"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"5082","DOI":"10.1016\/j.tcs.2009.08.006","volume":"410","author":"T. Batu","year":"2009","unstructured":"Batu, T., Berenbrink, P., Sohler, C.: A sublinear-time approximation scheme for bin packing. Theoretical Computer Science\u00a0410, 5082\u20135092 (2009)","journal-title":"Theoretical Computer Science"},{"key":"16_CR4","unstructured":"Brown, D.: A lower bound for on-line one-dimensional bin packing problem. Technical Report 864, University of Illinois, Urbana, IL (1979)"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1137\/S009753970444572X","volume":"35","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Liu, D., Magen, A.: Sublinear geometric algorithms. SIAM Journal on Computing\u00a035, 627\u2013646 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubfinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on Computing\u00a034, 1370\u20131379 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/3-540-48518-X_15","volume-title":"Algorithm Engineering and Experimentation","author":"J.A. Csirik","year":"1999","unstructured":"Csirik, J.A., Johnson, D.S., Kenyon, C., Shor, P.W., Weber, R.R.: A Self Organizing Bin Packing Heuristic. In: Goodrich, M.T., McGeoch, C.C. (eds.) ALENEX 1999. LNCS, vol.\u00a01619, pp. 246\u2013265. Springer, Heidelberg (1999)"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Csirik, J., Johnson, D., Kenyon, C., Orlin, J., Shore, P., Weber, R.: On the sum-of-squares algorithm for bin-packing. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 208\u2013217 (2000)","DOI":"10.1145\/335305.335331"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S0097539703435297","volume":"35","author":"A. Czumaj","year":"2005","unstructured":"Czumaj, A., Ergun, F., Fortnow, L., Magen, I.N.A., Rubinfeld, R., Sohler, C.: Sublinear approximation of euclidean minimum spanning tree. SIAM Journal on Computing\u00a035, 91\u2013109 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Estimating the weight of metric minimum spanning trees in sublinear-time. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 175\u2013183 (2004)","DOI":"10.1145\/1007352.1007386"},{"issue":"4","key":"16_CR11","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+epsilon in linear time. Combinatorica\u00a01(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P. Flajolet","year":"1985","unstructured":"Flajolet, P., Martin, G.: Probabilistic counting algorithms for data base application. Journal of Computer and System Sciences\u00a031, 182\u2013209 (1985)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10878-007-9092-2","volume":"15","author":"B. Fu","year":"2008","unstructured":"Fu, B., Chen, Z.: Sublinear-time algorithms for width-bounded geometric separators and their applications to protein side-chain packing problems. Journal of Combinatorial Optimization\u00a015, 387\u2013407 (2008)","journal-title":"Journal of Combinatorial Optimization"},{"key":"16_CR14","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Company, New York (1979)"},{"key":"16_CR15","unstructured":"Gilmore, M., Gomory, R.: A linear programming approach to the cutting-stock problem - part ii. Operations Research"},{"key":"16_CR16","unstructured":"Gilmore, M., Johnson, D.: A linear programming approach to the cutting-stock problem. Operations Research"},{"key":"16_CR17","unstructured":"Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Technical Report 00-20, Electronic Colloquium on Computational Complexity (2000), \n                  \n                    http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"issue":"2","key":"16_CR18","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M. Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: On the closest string and substring problems. Journal of the ACM\u00a049(2), 157\u2013171 (2002)","journal-title":"Journal of the ACM"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/S0020-0190(80)90077-0","volume":"10","author":"F. Liang","year":"1980","unstructured":"Liang, F.: A lower bound for on-line bin packing. Information Processing Letters\u00a010, 76\u201379 (1980)","journal-title":"Information Processing Letters"},{"key":"16_CR20","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (2000)"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"J.I. Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theoretical Computer Science\u00a012, 315\u2013323 (1980)","journal-title":"Theoretical Computer Science"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"S.G.O. Goldreich","year":"1998","unstructured":"Goldreich, S.G.O., Ron, D.: Property testing and its connection to learning and approximation. J. ACM\u00a045, 653\u2013750 (1998)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29700-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T00:34:41Z","timestamp":1558312481000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29700-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642296994","9783642297007"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29700-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}