Um QPTAS para o Problema de Empacotamento de Círculos em Linha - Dell’Arriva, Elisa; Miyazawa, Flávio K. (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
No problema de empacotamento de círculos em linha, é dada uma lista de círculos que devem ser dispostos lado a lado sobre uma linha horizontal, de forma que cada círculo toque a linha somente em seu ponto mais baixo. O objetivo é minimizar a distância entre os pontos mais à esquerda e mais à direita dos círculos que definem os extremos do empacotamento. Em 2018, [Dürr et al. 2018] mostraram um QPTAS para o caso em que os itens são triângulos retângulos isósceles. Neste texto, apresentamos uma adaptação desse QPTAS para o problema de empacotamento de círculos em linha.