A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

Resumen Técnico: Un Algoritmo de 2.37332-Competitivo para el Empaquetamiento en Línea de Cuadrados con Gravedad

Definición del Problema
El artículo aborda el problema de empaquetamiento en franjas en línea (online strip packing) para cuadrados con ejes paralelos bajo restricciones de Tetris y gravedad. En este modelo, los cuadrados llegan secuencialmente sin conocimiento de los elementos futuros y deben colocarse de forma irrevocable en una franja de ancho unitario y altura ilimitada.

• Restricción de Tetris: Un cuadrado entrante debe seguir una trayectoria descendente monótona y libre de colisiones desde arriba hasta su posición final.
• Restricción de Gravedad: El cuadrado debe descansar sobre el fondo de la franja o sobre la superficie superior de cuadrados colocados previamente.
• Factibilidad: Una región geométricamente vacía puede ser inutilizable si es inalcanzable mediante una trayectoria descendente o carece de soporte.

El objetivo es minimizar la altura total del empaquetado. El rendimiento se mide mediante la razón competitiva asintótica ($CR$), definida como el ínfimo de $\rho$ tal que $A(\sigma) \le \rho \cdot OPT(\sigma) + \beta$ para todas las secuencias de entrada $\sigma$, donde $A(\sigma)$ es la altura del algoritmo y $OPT(\sigma)$ es la altura óptima offline.

Metodología: AsymmetricSlots
El autor introduce AsymmetricSlots, un algoritmo recursivo que mejora el enfoque anterior conocido como SlotAlgorithm (Fekete et al., 2014), el cual utilizaba una jerarquía diádica (simétrica).

1. Jerarquía Asimétrica:
   En lugar de dividir un espacio (slot) de ancho $w$ en dos mitades iguales, el algoritmo lo divide en un hijo ancho de ancho $pw$ y un hijo estrecho de ancho $qw$, donde $p \in (1/2, 1)$ y $q = 1-p$. Esta jerarquía se fija antes de que lleguen los elementos.

2. Reglas de Enrutamiento Local:
   Al llegar, un cuadrado de lado $a$ desciende por la jerarquía basándose en su tamaño relativo al ancho actual del espacio $w$:

   • Directo: Si $a > pw$, el cuadrado se asigna al espacio actual inmediatamente.
   • Forzado: Si $qw < a \le pw$, el cuadrado es forzado hacia el hijo ancho.
   • Flexible: Si $a \le qw$, el cuadrado se enruta al hijo con la altura virtual actual más pequeña (rompiendo empates a favor del hijo ancho).

3. Perfil de Altura Virtual y Factibilidad:
   El algoritmo mantiene un perfil de altura virtual de constante por tramos $h(x)$ para guiar el enrutamiento. Un cuadrado asignado a un espacio $T$ actualiza la altura virtual del intervalo de ese espacio por su longitud de lado $a$.

   • La Lema 1 demuestra que, a pesar de que el perfil virtual pueda sobreestimar la altura física, la inserción física es siempre factible bajo las restricciones de Tetris y gravedad. Específicamente, el cuadrado físico siempre puede caer a un nivel de soporte $y^*$ (determinado por los cuadrados existentes o el fondo de la franja) que es $\le$ el nivel de actualización virtual, asegurando que no ocurran colisiones durante el descenso.

4. Análisis mediante Cargo Local:
   La prueba utiliza un invariante de fase local y un argumento de cargo (charging argument) que explota la asimetría de la división:

   • Cuadrados Forzados: Los cuadrados grandes ($a > qw$) son forzados en trayectorias específicas. Su área es suficiente para "pagar" la altura que crean ($wa - \rho a^2 \le 0$).
   • Cuadrados Flexibles: Los cuadrados pequeños ($a \le qw$) permiten el equilibrio entre los hijos. El análisis utiliza un conteo "basado en fases" donde el algoritmo mantiene un crédito $\delta w^2$. La asimetría asegura que la pérdida asociada con las colocaciones flexibles esté acotada localmente y no se acumule con la profundidad de la jerarquía.
   • Cierre de Fase: Una fase en un espacio termina cuando se coloca un cuadrado "directo" (uno demasiado grande para los hijos), reiniciando el perfil virtual.

Resultados Clave

1. Límite Superior Mejorado para Cuadrados:
   Al optimizar el parámetro de división $p$, el autor deriva una razón competitiva de 2.373318506....

   • El parámetro óptimo $p^\star$ es la raíz única en $(1/2, 1)$ de $16p^3 - 8p^2 + p - 1 = 0$, lo que resulta en $p^\star \approx 0.5786$.
   • La razón resultante es $\rho^\star = 1/(1-p^\star) \approx 2.3733$.
   • Una aproximación racional usando $p = 11/19$ produce una razón limpia de 2.375 ($19/8$).
   • Esto mejora el mejor límite superior previo de $34/13 \approx 2.6154$ establecido por Fekete et al.

2. Límite Inferior para el Algoritmo:
   El artículo establece un límite inferior específico para AsymmetricSlots. Mediante una construcción de cuadrados repetidos, demuestran que para un $p$ en un rango que contiene a $p^\star$, la razón competitiva es al menos 2.

   • Por lo tanto, $2 \le CR(AsymmetricSlots_{p^\star}) \le 2.3733...$
   • El límite inferior general para cualquier algoritmo en línea determinista en este modelo sigue siendo $3/2$ (de Fekete et al.).

3. Extensión a Rectángulos:
   El marco se extiende a rectángulos con una relación de aspecto $\kappa$ acotada (donde el ancho $u$ y la altura $v$ satisfacen $u/\kappa \le v \le \kappa u$).

   • Límite Superior: El algoritmo logra una razón competitiva asintótica de $O(\kappa)$.
   • Límite Inferior: Se demuestra un límite inferior de $\Omega(\kappa)$ mediante una construcción alternante de rectángulos verticales delgados y rectángulos anchos y poco profundos.
   • Esto establece que la dependencia óptima de la relación de aspecto es $\Theta(\kappa)$.

Significado y Reivindicaciones
El artículo afirma proporcionar el mejor límite superior conocido para el problema de empaquetamiento de cuadrados en línea con restricciones de Tetris y gravedad, reduciendo la razón competitiva de $\approx 2.6154$ a $\approx 2.3733$.

• Contribución Metodológica: El cambio de una descomposición recursiva simétrica (diádica) a una descomposición asimétrica permite un argumento de cargo local más eficiente. La asimetría separa las colocaciones en categorías "forzadas" (grandes) y "flexibles" (pequeñas), evitando la acumulación de términos de error que afectaron a los análisis anteriores.
• Alcance: Los resultados son estrictamente teóricos, centrados en el análisis competitivo de algoritmos deterministas. El artículo no pretende resolver el problema offline general ni proporcionar un esquema de aproximación de tiempo polinomial para el caso offline.
• Limitaciones: El autor señala que la brecha entre el límite inferior específico del algoritmo (2) y el límite superior (2.3733) persiste, al igual que la brecha entre el límite inferior general (1.5) y el límite superior. El artículo sugiere que trabajos futuros podrían explorar divisiones no autosimilares o más de dos subespacios para potencialmente cerrar estas brechas.

En resumen, el trabajo refina los límites teóricos del empaquetamiento de cuadrados en línea bajo restricciones físicas, demostiendo que la descomposición jerárquica asimétrica produce una razón competitiva estrictamente mejor que los enfoques simétricos conocidos anteriormente.