Seminário de Teoria da Computação Packing Problems with Orthogonal Rotations Flávio K. Miyazawa Sexta-feira, 19 de setembro de 2003 Auditório do IC (IC1), 13:00hs We consider 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^\circ rotations are allowed. For the strip packing problem we present an algorithm with asymptotic performance bound 1.613; for the two-dimensional bin packing problem we present an algorithm with asymptotic performance bound 2.64; for the three-dimensional strip packing problem, we present an algorithm with asymptotic performance bound 2.76, and for the three-dimensional bin packing problem we present an algorithm with asymptotic performance bound 4.89. 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. In this talk, we will present some ideas on this algorithms. This is a joint work with Y. Wakabayashi and has the collaboration of P. Raghavan.