05 April 2023
14:00 Master's Defense IC3 Auditorium
Theme
Approximation Algorithms for the Two-Dimensional Least Sum Packing Problem
Student
Rachel Vanucchi Saraiva
Advisor / Teacher
Rafael Crivellari Saliba Schouery
Brief summary
The work deals with the minimum sum variant of the packing problem for square items, in which a list of square items must be packed in square containers of dimensions 1 x 1, the cost of packing each item is equal to the index of the container in which it is packed , and the objective is to minimize the total cost of packing all the items. The problem has applications in the minimization of the average time of logistical operations such as cutting and delivery of products. In this work we prove that classical algorithms for two-dimensional packing that sort items in non-increasing order of size, such as Hybrid First Fit, are arbitrarily bad for this variant of the problem. We then present a 5/2-approximation and a PTAS for the variant.
Examination Board
Headlines:
| Rafael Crivellari Saliba Schouery | IC / UNICAMP |
| Lehilton Lelis Chaves Pedrosa | IC / UNICAMP |
| Yoshiko Wakabayashi | IME / USP |
Substitutes:
| Flávio Keidi Miyazawa | IC / UNICAMP |
| Carla Negri Lintzmayer | CMCC / UFABC |