💻 computer science

A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

Este artigo introduz o algoritmo $\mathrm{AsymmetricSlots}$ , que alcança uma razão de competitividade de 2,37332 para o empacotamento de quadrados online em uma faixa de largura unitária sob restrições de Tetris e gravidade, melhorando o limite anterior de aproximadamente 2,6154 e estabelecendo também a dependência ótima em relação à razão de aspecto para retângulos gerais.

Autores originais: Nichlas Langhoff Rasmussen

Publicado 2026-09-10

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Nichlas Langhoff Rasmussen

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um mundo onde você deve construir uma torre, um bloco de cada vez, sem nunca ver o que vem a seguir. Você não pode rearranjar os blocos que já colocou e não pode alcançar a estrutura para movê-los de lado. Cada novo bloco deve cair de cima, caindo em linha reta até atingir o topo da pilha existente ou o chão. Se existir uma lacuna na torre, mas ela estiver bloqueada por cima por um bloco mais largo, essa lacuna é inútil; nada poderá alcançá-la. Este é o desafio do empacotamento online sob gravidade, um problema que se situa na interseção entre a geometria e a logística. Ele faz uma pergunta simples, porém obstinada: como pode um sistema tomar as melhores decisões possíveis quando é cego ao futuro e está limitado pelas leis da física?

Durante anos, o melhor método conhecido para empilhar blocos quadrados desta maneira podia garantir uma torre que não fosse mais do que cerca de 2,62 vezes mais alta do que a torre absolutamente mais curta possível se alguém tivesse visto todos os blocos com antecedência. Essa lacuna entre a realidade online e o ideal offline representava uma ineficiência significativa. Pesquisadores há muito suspeitavam que uma maneira mais inteligente de organizar o espaço poderia fechar essa lacuna, mas as restrições da gravidade e a falta de previsão tornavam a busca por tal método excepcionalmente difícil. O problema não é apenas sobre encaixar formas; é sobre gerenciar o fluxo de espaço à medida que ele é consumido, garantindo que o caminho para os futuros blocos permaneça aberto mesmo enquanto a estrutura atual cresce.

Um estudo recente introduz uma nova estratégia chamada AsymmetricSlots, que consegue estreitar com sucesso essa lacuna de eficiência. Os pesquisadores desenvolveram um método que melhora o desempenho no pior caso do algoritmo de empacotamento, provando que a torre resultante nunca será mais do que aproximadamente 2,37 vezes a altura da torre perfeita e pré-planejada. Este é um progresso mensurável em relação ao melhor resultado anterior, aproximando o limite teórico do empacotamento de quadrados online do ideal. O trabalho não afirma ter resolvido o problema inteiramente, pois permanece uma lacuna entre este novo limite superior e o limite inferior conhecido de 2, mas estabelece um novo padrão mais elevado para o que é alcançável.

O cerne desta nova abordagem reside em como o espaço disponível é dividido. Métodos anteriores tratavam a faixa vertical de espaço como uma série de compartimentos concêntricos de tamanhos iguais, dividindo a largura ao meio em cada nível. O novo algoritmo quebra essa simetência. Em vez de dividir o espaço uniformemente, ele divide cada slot disponível em dois filhos desiguais: um largo e um estreito. Quando um quadrado chega, o algoritmo decide para onde enviá-lo com base no seu tamanho em relação a essas divisões desiguais. Se um quadrado for grande demais para o filho estreito, ele é forçado para o filho largo. Se for pequeno o suficiente para caber em ambos, o algoritmo o envia para o filho que possui atualmente a pilha de blocos mais baixa. Esse processo de tomada de decisão local, repetido conforme o quadrado desce pela hierarquia de slots, permite que o sistema equilibre a carga de forma mais eficaz do que os antigos métodos simétricos.

Para provar que essa estratégia funciona, os pesquisadores utilizaram um método de contabilidade que rastreia o "custo" de cada quadrado colocado. Eles imaginaram que cada quadrado paga pela altura que adiciona à torre usando sua própria área como moeda. Quadrados grandes, que são forçados para slots específicos, pagam diretamente por sua própria altura. Quadrados menores, que possuem a flexibilidade de escolher entre slots, são gerenciados através de um sistema de créditos temporários que se equilibram ao longo do tempo. A análise mostra que a perda de eficiência causada por essas escolhas flexíveis não se acumula conforme a torre cresce; em vez disso, ela permanece limitada. Esta prova matemática confirma que o desempenho do algoritmo é estável e previsível, independentemente da sequência de blocos que ele recebe.

O estudo também estende essa lógica para retângulos que não são quadrados perfeitos, mas que são limitados em quão longos e finos podem ser. Para essas formas, os pesquisadores descobriram que a eficiência do empacotamento depende diretamente da razão máxima entre o comprimento e a largura de um retângulo. Eles provaram que, à medida que essa razão aumenta, a dificuldade de empacotar aumenta de uma forma linear e previsível. Este resultado sugere que o método é robusto e pode ser adaptado a uma variedade maior de formas, desde que as formas não se tornem infinitamente finas. Por outro outro lado, eles também demonstraram que nenhum algoritmo online pode fazer significativamente melhor do que essa relação linear, o que significa que a dependência das proporções da forma é fundamental para o próprio problema.

Embora o novo algoritmo represente um passo significativo à frente, os pesquisadores fazem questão de notar que o problema ainda não foi totalmente resolvido. Eles construíram cenários específicos onde o novo algoritmo produz uma torre duas vezes mais alta do que a solução offline ideal, mostrando que a lacuna entre o melhor desempenho online possível e o ideal teórico ainda é substancial. A diferença entre o novo limite superior de aproximadamente 2,37 e o limite inferior de 2 continua sendo um grande abismo para os matemáticos superarem. No entanto, ao estabelecer um novo limite mais estreito e fornecer um arcabouço que lida tanto com quadrados quanto com retângulos limitados, este trabalho esclarece o panorama do problema. Ele mostra que, com o tipo certo de organização assimétrica, as restrições da gravidade e da ignorância do futuro podem ser gerenciadas com maior precisão do que se pensava anteriormente possível.

Resumo Técnico: Um Algoritmo Competitivo de 2,37332 para Empacotamento de Quadrados Online com Gravidade

Definição do Problema
O artigo aborda o problema de empacotamento de tiras online (online strip packing) para quadrados axiais paralelos sob restrições de Tetris e gravidade. Neste modelo, os quadrados chegam sequencialmente sem conhecimento de itens futuros e devem ser posicionados de forma irrevogável em uma tira de largura unitária e altura ilimitada.

Restrição de Tetris: Um quadrado que chega deve seguir um caminho descendente monotônico e livre de colisões de cima para sua posição final.
Restrição de Gravidade: O quadrado deve repousar sobre o fundo da tira ou sobre a superfície superior de quadrados previamente posicionados.
Viabilidade: Uma região geometricamente vazia pode ser inutilizável se for inalcançável via um caminho descendente ou se carecer de suporte.

O objetivo é minimizar a altura total do empacotamento. O desempenho é medido pela razão competitiva assintótica ( $CR$ ), definida como o ínfimo de $\rho$ tal que $A(\sigma) \le \rho \cdot OPT(\sigma) + \beta$ para todas as sequências de entrada $\sigma$ , onde $A(\sigma)$ é a altura do algoritmo e $OPT(\sigma)$ é a altura ótima offline.

Metodologia: AsymmetricSlots
O autor introduz o AsymmetricSlots, um algoritmo recursivo que melhora a abordagem anterior conhecida, SlotAlgorithm (Fekete et al., 2014), que utilizava uma hierarquia diádica (simétrica).

Hierarquia Assimétrica:
Em vez de dividir um slot de largura $w$ em dois meios iguais, o algoritmo o divide em um filho largo de largura $pw$ e um filho estreito de largura $qw$, onde $p \in (1/2, 1)$ e $q = 1-p$ . Esta hierarquia é fixa antes de qualquer item chegar.
Regras de Roteamento Local:
Ao chegar, um quadrado de lado $a$ desce a hierarquia com base em seu tamanho relativo à largura atual do slot $w$ :

Direto (Direct): Se $a > pw$, o quadrado é atribuído ao slot atual imediatamente.
Forçado (Forced): Se $qw < a \le pw$ , o quadrado é forçado para o filho largo.
Flexível (Flexible): Se $a \le qw$ , o quadrado é roteado para o filho com a menor altura virtual atual (com empates decididos em favor do filho largo).

Perfil de Altura Virtual e Viabilidade:
O algoritmo mantém um perfil de altura virtual de constante por partes $h(x)$ para guiar o roteamento. Um quadrado atribuído a um slot $T$ atualiza a altura virtual do intervalo desse slot pelo seu lado $a$ .

Lema 1 prova que, apesar do perfil virtual potencialmente superestimar a altura física, a inserção física é sempre viável sob as restrições de Tetris e gravidade. Especificamente, o quadrado físico pode sempre cair para um nível de suporte $y^*$ (determinado pelos quadrados existentes ou pelo fundo da tira) que é $\le$ o nível de atualização virtual, garantindo que não ocorram colisões durante a descida.

Análise via Cobrança Local (Local Charging):
A prova utiliza um invariante de fase local e um argumento de cobrança que explora a assimetria da divisão:

Quadrados Forçados: Quadrados grandes ($a > qw$) são forçados em caminhos específicos. Sua área é suficiente para "pagar" pela altura que criam ( $wa - \rho a^2 \le 0$ ).
Quadrados Flexíveis: Quadrados pequenos ( $a \le qw$ ) permitem o balanceamento entre os filhos. A análise utiliza uma "contabilidade baseada em fases" onde o algoritmo mantém um crédito $\delta w^2$ . A assimetria garante que a perda associada aos posicionamentos flexíveis seja limitada localmente e não se acumule com a profundidade da hierarquia.
Fechamento de Fase: Uma fase em um slot termina quando um quadrado "direto" (um quadrado grande demais para os filhos) é posicionado, resetando o perfil virtual.

Resultados Principais

Melhoria do Limite Superior para Quadrados:
Ao otimizar o parâmetro de divisão $p$ , o autor deriva uma razão competitiva de 2,373318506....

O parâmetro ótimo $p^\star$ é a raiz única em $(1/2, 1)$ de $16p^3 - 8p^2 + p - 1 = 0$ , resultando em $p^\star \approx 0,5786$ .
A razão resultante é $\rho^\star = 1/(1-p^\star) \approx 2,3733$ .
Uma aproximação racional usando $p = 11/19$ produz uma razão limpa de 2,375 ( $19/8$ ).
Isso melhora o limite superior anterior de $34/13 \approx 2,6154$ estabelecido por Fekete et al.

Limite Inferior para o Algoritmo:
O artigo estabelece um limite inferior específico para o AsymmetricSlots. Usando uma construção de quadrados repetidos, eles mostram que, para $p$ em um intervalo contendo $p^\star$ , a razão competitiva é pelo menos 2.

Assim, $2 \le CR(AsymmetricSlots_{p^\star}) \le 2,3733...$
O limite inferior geral para qualquer algoritmo online determinístico neste modelo permanece $3/2$ (de Fekete et al.).

Extensão para Retângulos:
O framework é estendido para retângulos com uma razão de aspecto $\kappa$ limitada (onde largura $u$ e altura $v$ satisfazem $u/\kappa \le v \le \kappa u$ ).

Limite Superior: O algoritmo alcança uma razão competitiva assintótica de $O(\kappa)$ .
Limite Inferior: Um limite inferior correspondente $\Omega(\kappa)$ é provado via uma construção alternada de retângulos verticais finos e retângulos horizontais rasos.
Isso estabelece que a dependência ótima da razão de aspecto é $\Theta(\kappa)$ .

Significância e Alegações
O artigo alega fornecer o melhor limite superior conhecido para o problema de empacotamento de quadrados online com restrições de Tetris e gravidade, reduzindo a razão competitiva de $\approx 2,6154$ para $\approx 2,3733$ .

Contribuição Metodológica: A mudança de uma decomposição recursiva simétrica (diádica) para uma decomposição assimétrica permite um argumento de cobrança local mais eficiente. A assimetria separa os posicionamentos em categorias "forçadas" (grandes) e "flexíveis" (pequenas), evitando o acúmulo de termos de erro que prejudicaram análises anteriores.
Escopo: Os resultados são estritamente teóricos, focando na análise competitiva de algoritmos determinísticos. O artigo não pretende resolver o problema offline geral ou fornecer um esquema de aproximação de tempo polinomial para o caso offline.
Limitações: O autor observa que a lacuna entre o limite inferior específico do algoritmo (2) e o limite superior (2,3733) permanece, assim como a lacuna entre o limite inferior geral (1,5) e o limite superior. O artigo sugere que trabalhos futuros podem explorar divisões não auto-similares ou mais de dois sub-slots para potencialmente fechar essas lacunas.

Em resumo, o trabalho refina os limites teóricos do empacotamento de quadrados online sob restrições físicas, demonstrando que a decomposição hierárquica assimétrica produz uma razão competitiva estritamente melhor do que as abordagens simétricas conhecidas anteriormente.

Mais como este