Resumo: Problemas de empacotamento com número fixo de recipientes consistem em, dado um conjunto de itens e um número de recipientes de uma determinada capacidade, empaco tar um subconjunto dos itens nos recipientes, maximizando ou minimizando uma certa função objetivo, tal como a soma dos valores dos itens empacotados. O Binary Knapsack Problem (KP), o Generalized Assignment Problem (GAP), o Multiple Knapsack Problem (MKP) e o Bin Packing Problem (BPP) são exemplos clássicos de problemas de empacotamento, mas apenas o KP, o GAP e o MKP possuem número fixo de recipientes, já que o BPP permite que novos recipientes sejam criados. Outros problemas com essa característica são o Maxspace, o Positional Knapsack Problem e o Extensible Bin Packing. O Maxspace é um problema de disposição de propagandas, no qual desejamos exibir propagandas em um banner, maximizando a área ocupada pelas propagandas exibidas. O Positional Knapsack Problem é uma variante do Binary Knapsack Problem em que desejamos colocar itens em um recipiente e o valor do item pode variar de acordo com a posição que é empacotado. Já o Extensible Bin Packing (EBP) é um problema de empacotamento em que desejamos adicionar uma quantidade de itens em um número fixo de recipientes de mesmo tamanho, mas, diferentemente dos Maxspace e do PKP, o EBP exige que todos os itens sejam empacotados e permite que os recipientes sejam estendidos, aumentando o custo da solução proporcionalmente ao valor total de extensão. Neste trabalho, apresentamos um Polynomial-Time Approximation Scheme (PTAS) para uma variante do Maxspace, um Fully Polynomial-Time Approximation Scheme (FPTAS) para uma função de variação específica do PKP e um PTAS para o PKP com um conjunto de funções mais geral. Além disso, apresentamos algoritmos utilizando a formulação arc-flow e a técnica de branch-and-cut-and-price para o EBP Ver menos

Abstract: Packing problems with a fixed number of bins consist of, given a set of items and several bins of a given capacity, packing a subset of the items in the bins, maximizing or minimiz- ing a certain objective function, such as the sum of the values of the packed items. The Bi nary Knapsack Problem (KP), the Generalized Assignment Problem (GAP), the Multiple Knapsack Problem (MKP), and the Bin Packing Problem (BPP) are classic examples of packing problems, but only KP, GAP and MKP have a fixed number of bins since BPP allows new bins to be created. Other problems with this char- acteristic are Maxspace, Positional Knapsack Problem, and Extensible Bin Packing. The Maxspace is an advertising placement problem in which we want to display advertisements on a banner, maximizing the area occupied by the advertisements displayed. The Positional Knapsack Problem is a variant of Binary Knapsack Problem in which we want to place items in a knapsack, and the item’s value can vary ac- cording to the position in which it is packed. And the Extensible Bin Packing (EBP) is a packing problem in which we want to place several items in a fixed number of bins of the same size, but, unlike Maxspace and PKP, EBP requires that all items be packed, and allows the bins to be extended, increasing the cost of the solution proportionally to the total value of the extension. The main objective of this work is to develop new approx- imation and exact algorithms for packing problems with a fixed number of bins, more specifically to Maxspace, Positional Knapsack Problem, and Extensible Bin Packing, taking into account variants found in practice for these problems. In this work, we present a Polynomial-Time Approximation Scheme (PTAS) for a variant of Maxs- pace, a Fully Polynomial-Time Approximation Scheme (FPTAS) for a specific variation function of PKP, and a PTAS for PKP with a more general set of functions. In addition, we present algorithms using the arc-flow formulation and the branch-and-cut-and-price technique for EBP Ver menos