Resumo: Problemas de empacotamento têm muitas aplicações práticas. Eles podem ser usados para modelar problemas como corte de materiais, armazenamento e transporte de mercadorias, escalonamento de processos e alocação de anúncios e propagandas, entre outros. Nesta dissertação, estamos interessados em problemas de empacotamento em que os objetos a serem empacotados possuem formas geométricas bidimensionais. Em particular, abordamos um problema que aqui chamamos de problema do Empacotamento de Círculos em Linha (In-line Circle Packing (ICP)). Neste problema, temos como entrada uma lista de círculos e queremos empacotá-los sobre uma linha horizontal de forma que cada círculo toque a linha por cima em exatamente um ponto, sem causar sobreposição dos círculos. O objetivo é minimizar o span do empacotamento, isto é, minimizar a distância entre o ponto mais à esquerda e o ponto mais à direita do empacotamento. Como acontece com a maioria dos problemas de empacotamento, o ICP é NP-difícil. Isso significa que não existe algoritmo capaz de produzir uma solução ótima em tempo polinomial, a menos que P = NP. Sendo assim, uma forma natural de investigar esses problemas é obter de forma eficiente soluções cujos valores estejam próximos do valor ótimo. Uma abordagem nessa direção é a dos Algoritmos de Aproximação. Em termos gerais, algoritmos de aproximação são algoritmos eficientes que produzem uma solução com garantia de qualidade em relação à solução ótima, para todas as instâncias do problema. Neste trabalho, estamos particularmente interessados em algoritmos de aproximação que produzem soluções cujos valores estão dentro de um fator do valor de uma solução ótima. Apresentamos alguns resultados encontrados na literatura para o ICP, como uma prova de sua NP-dificuldade e um algoritmo de aproximação de fator constante. Mostramos um PTAS simples para uma versão restrita do problema ICP, em que todos os círculos têm raio cujo valor é pelo menos uma constante. Além disso, investigamos uma versão do ICP em bins, que chamamos de problema do Empacotamento de Círculos em Linha em Bins (In-line Circle Bin Packing (ICB)). Nesta versão, devemos empacotar os círculos dentro de bins e cada círculo deve tocar o fundo da bin em exatamente um ponto. Mostramos um APTAS para esta variante restrito a grandes círculos em bins aumentadas Ver menos

Abstract: Packing problems have many practical applications. They can be used to model problems such as cutting stock, storage and transportation of goods, processes scheduling, and allocation of advertisements, among others. In this dissertation, we are interested in packing problems where the objects to be packed have two-dimensional forms. In particular, we address a problem we call here In-line Circle Packing (ICP) problem. In this problem we have as input a list of circles, and we want to pack the circles on a horizontal line in a way that each circle touches the line from above at exactly one point, without causing overlap of the circles. The goal is to minimize the span of the packing, i.e., minimize the distance between the leftmost and the rightmost points of the packing. As it happens with the majority of the packing problems, the ICP is NP-hard. This means that there is no algorithm capable of producing an optimal solution in polynomial time, unless P = NP. That being the case, one natural way to investigate these problems is to efficiently obtain solutions whose values ??are close to the optimal value. One approach in this direction is that of Approximation Algorithms. In general terms, approximation algorithms are efficient algorithms that produce a solution with a guarantee of quality in relation to the optimal solution, for every instance of the problem. In this work, we are particularly interested in approximation algorithms that produce solutions whose values are within a factor of the value of an optimal solution. We present some results found in the literature for the ICP problem, such as a proof of its NP-hardness and a constant factor approximation algorithm. We show a simple PTAS for a restricted version of the ICP problem, where all circles have radius whose value is at least a constant. In addition, we investigate a version of the ICP in bins, which we call the In-line Circle Bin Packing (ICB) problem. In this version, we must pack the circles inside bins and every circle must touch the bottom of the bin at exactly one point. We show an APTAS for this variant restricted to large circles in augmented bins Ver menos