Packing Problems With Orthogonal Rotations

dc.creatorMiyazawa F.K.
dc.creatorWakabayashi Y.
dc.date2004
dc.date2015-06-26T14:23:51Z
dc.date2015-11-26T14:12:31Z
dc.date2015-06-26T14:23:51Z
dc.date2015-11-26T14:12:31Z
dc.date.accessioned2018-03-28T21:13:10Z
dc.date.available2018-03-28T21:13:10Z
dc.identifier
dc.identifierLecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). , v. 2976, n. , p. 359 - 368, 2004.
dc.identifier3029743
dc.identifier
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-35048854563&partnerID=40&md5=e2752a223fff5de1b21e3f71a64c0568
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/94271
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/94271
dc.identifier2-s2.0-35048854563
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1242022
dc.descriptionIn this extended abstract, we present approximation algorithms for the following packing problems: the strip packing problem, the two-dimensional bin packing problem, the three-dimensional strip packing problem, and the three-dimensional bin packing problem. For all these problems, we consider orthogonal packings where 90° rotations are allowed. The algorithms we show for these problems have asymptotic performance bounds 1.613, 2.64, 2.76 and 4.89, respectively. We also present an algorithm for the z-oriented three-dimensional packing problem with asymptotic performance bound 2.64. To our knowledge the bounds presented here are the best known for each problem. © Springer-Verlag 2004.
dc.description2976
dc.description
dc.description359
dc.description368
dc.descriptionBaker, B.S., Coffman Jr., E.G., Rivest, R.L., Orthogonal packings in two-dimensions (1980) SIAM Journal on Computing, 9, pp. 846-855
dc.descriptionChung, F.R.K., Garey, M.R., Johnson, D.S., On packing two-dimensional bins (1982) SIAM Journal on Algebraic and Discrete Methods, 3, pp. 66-76
dc.descriptionCoffman Jr., E.G., Garey, M.R., Johnson, D.S., Approximation algorithms for bin packing - An updated survey (1984) Algorithms Design for Computer System Design, pp. 49-106. , G. Ausiello, M. Lucertini, and P. Serafini, editors, Spring-Verlag, New York
dc.descriptionCoffman Jr., E.G., Garey, M.R., Johnson, D.S., (1997) Approximation Algorithms, , ed. D. Hochbaum, chapter Approximation algorithms for bin packing - a survey. PWS
dc.descriptionCoffman Jr., E.G., Garey, M.R., Johnson, D.S., Tarjan, R.E., Performance bounds for level oriented two-dimensional packing algorithms (1980) SIAM J. on Computing, 9, pp. 808-826
dc.descriptionDe La Fernandez Vega, W., Lueker, G.S., Bin packing can be solved within 1 + ε in linear time (1981) Combinatorica, 1 (4), pp. 349-355
dc.descriptionJohnson, D.S., (1973) Near-optimal Bin Packing Algorithms, , PhD thesis, Massachusetts Institute of Technology, Cambridge, Mass
dc.descriptionKenyon, C., Remila, E., Approximate strip packing (1996) 37th Annual Symposium on Foundations of Computer Science, pp. 31-36
dc.descriptionLi, K., Cheng, K.-H., Static job scheduling in partitionable mesh connected systems (1990) Journal of Parallel and Distributed Computing, 10, pp. 152-159
dc.descriptionMiyazawa, F.K., Wakabayashi, Y., An algorithm for the three-dimensional packing problem with asymptotic performance analysis (1997) Algorithmica, 18 (1), pp. 122-144
dc.descriptionMiyazawa, F.K., Wakabayashi, Y., Approximation algorithms for the orthogonal z-oriented 3-D packing problem (2000) SIAM Journal on Computing, 29 (3), pp. 1008-1029
dc.descriptionVazirani, V.V., (2001) Approximation Algorithms, , Springer-Verlag
dc.languageen
dc.publisher
dc.relationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.rightsfechado
dc.sourceScopus
dc.titlePacking Problems With Orthogonal Rotations
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución