Problema con la tapa del contenedor

En el problema de cubrir contenedores , los artículos de diferentes tamaños deben empaquetarse en un número finito de contenedores, cada uno de los cuales debe contener al menos un tamaño total determinado, de manera que se maximice el número de contenedores utilizados.

Este problema es dual al problema de empaquetamiento de contenedores : en el problema de cobertura de contenedores, los tamaños de los contenedores están limitados inferiormente y el objetivo es maximizar su número; en el problema de empaquetamiento de contenedores, los tamaños de los contenedores están limitados superiormente y el objetivo es minimizar su número. ^{[ 1 ]}

El problema es NP-difícil , pero existen varios algoritmos de aproximación eficientes :

Algoritmos que cubren al menos 1/2, 2/3 o 3/4 del número óptimo de intervalos de forma asintótica, ejecutándose en tiempo $O(n),O(n\log n),O(n{\log }^{2}n)$ respectivamente. ^{[ 1 ]}^{[ 2 ]}
Un PTAS asintótico , algoritmos con comportamiento en el peor caso acotado cuyo comportamiento esperado es asintóticamente óptimo para algunas distribuciones discretas, y un algoritmo de aprendizaje con comportamiento esperado asintóticamente óptimo para todas las distribuciones discretas. ^{[ 3 ]}
Un FPTAS asintótico . ^{[ 4 ]}

El algoritmo de llenado de contenedores bidireccional

Csirik, Frenk, Lebbe y Zhang ^{[ 2 ]}^{: 16–19} presentan el siguiente algoritmo simple para la aproximación 2/3. Supongamos que el tamaño del contenedor es 1 y hay n elementos.

Ordena los elementos del más grande (1) al más pequeño ( n ).
Llena un contenedor con los artículos más grandes : 1, 2, ..., m , donde m es el entero más grande para el cual la suma de los artículos 1, ..., m es menor que 1.
Agregue a este contenedor los elementos más pequeños : n , n -1, ..., hasta que su valor supere 1.

Para cualquier instancia I , denotemos por $\mathrm {OPT} (I)$ el número de contenedores en la solución óptima, y por $\mathrm {BDF} (I)$ el número de contenedores llenos en el algoritmo de llenado bidireccional. Entonces $\mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I)-(2/3)$ , o equivalentemente, $\mathrm {OPT} (I)\leq (3/2)\mathrm {BDF} (I)+1$ .

Prueba

Para la demostración se utiliza la siguiente terminología.

$t:=\mathrm {BDF} (I)=$ el número de contenedores llenados por el algoritmo.
$B_{1},\ldots ,B_{t}:=$ los contenedores t llenados por el algoritmo.
Elementos iniciales : los t elementos que se insertan primero en cada uno de los t contenedores.
Artículos finales : los t artículos que se insertan al final en cada uno de los t contenedores.
Elementos intermedios : todos los elementos que no son ni iniciales ni finales.
$w$ := the number of final items that are at most 1/2 (equivalently, $tw$ is the number of final items larger than 1/2).

The sum of each bin $B_{1},\ldots ,B_{t}$ is at least 1, but if the final item is removed from it, then the remaining sum is smaller than 1. Each of the first $w$ bins $B_{1},\ldots ,B_{w}$ contains an initial item, possibly some middle items, and a final item. Each of the last $tw$ bins $B_{w+1},\ldots ,B_{t}$ contains only an initial item and a final item, since both of them are larger than 1/2 and their sum is already larger than 1.

The proof considers two cases.

The easy case is $w=t$ , that is, all final items are smaller than 1/2. Then, the sum of every filled $B_{i}$ is at most 3/2, and the sum of remaining items is at most 1, so the sum of all items is at most $3t/2+1$ . On the other hand, in the optimal solution the sum of every bin is at least 1, so the sum of all items is at least $\mathrm {OPT} (I)$ . Therefore, $\mathrm {OPT} (I)\leq 3t/2+1$ as required.

The hard case is $w<t$ , that is, some final items are larger than 1/2. We now prove an upper bound on $\mathrm {OPT} (I)$ by presenting it as a sum $\mathrm {OPT} (I)=|K_{0}|+|K_{1}|+|K_{2}|$ where:

$K_{0}:=$ the optimal bins with no initial/final items (only middle items).
$K_{1}:=$ the optimal bins with exactly one initial/final item (and some middle items).
$K_{2}:=$ the optimal bins with two or more initial/final items (and some middle items).

We focus first on the optimal bins in $K_{0}$ and $K_{1}$ . We present a bijection between the items in each such bin to some items in $B_{1},\ldots ,B_{t}$ which are at least as valuable.

The single initial/final item in the $K_{1}$ bins is mapped to the initial item in $B_{1},\ldots ,B_{|K_{1}|}$ . Note that these are the largest initial items.
The middle items in the $K_{0}$ and $K_{1}$ bins are mapped to the middle items in $B_{1},\ldots ,B_{w}$ . Note that these bins contain all the middle items.
Therefore, all items in $K_{0}$ and $K_{1}$ are mapped to all non-final items in $B_{1},\ldots ,B_{|K_{1}|}$ , plus all middle items in $B_{|K_{1}|+1},\ldots ,B_{w}$ .
The sum of each bin $B_{1},\ldots ,B_{w}$ without its final item is less than 1. Moreover, the initial item is more than 1/2, so the sum of only the middle items is less than 1/2. Therefore, the sum of all non-final items in $B_{1},\ldots ,B_{|K_{1}|}$ , plus all middle items in $B_{|K_{1}|+1},\ldots ,B_{w}$ , is at most $|K_{1}|+(w-|K_{1}|)/2=(|K_{1}|+w)/2$ .
The sum of each optimal bin is at least 1. Hence: $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ , which implies $2|K_{0}|+|K_{1}|\leq w\leq t$ .

We now focus on the optimal bins in $K_{1}$ and $K_{2}$ .

The total number of initial/final items in the $K_{1}$ and $K_{2}$ bins is at least $|K_{1}|+2|K_{2}|$ , but their total number is also $2t$ since there are exactly two initial/final items in each bin. Therefore, $|K_{1}|+2|K_{2}|\leq 2t$ .
Summing the latter two inequalities implies that $2\mathrm {OPT} (I)\leq 3t$ , which implies $\mathrm {OPT} (I)\leq 3t/2$ .

Tightness

The 2/3 factor is tight for BDF. Consider the following instance (where $\epsilon >0$ is sufficiently small): ${\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 6k~{\text{units}}\cdots \}~&~\{\cdots 6k~{\text{units}}\cdots \}\end{aligned}}$ BDF initializes the first bin with the largest item and fills it with the $6k$ smallest items. Then, the remaining $6k$ items can cover bins only in triplets, so all in all $2k+1$ bins are filled. But in OPT one can fill $3k$ bins, each of which contains two of the middle-sized items and two small items.

Three-classes bin-filling algorithm

Csirik, Frenk, Lebbe y Zhang ^{[ 2 ]}^{: 19–24} presentan otro algoritmo que alcanza una aproximación de 3/4. El algoritmo ordena los elementos de mayor a menor y los divide en tres clases:

X: Los artículos con un tamaño mínimo de 1/2;
Y: Los artículos con un tamaño menor a 1/2 y al menos 1/3;
Z: Los artículos con un tamaño menor a 1/3.

El algoritmo funciona en dos fases. Fase 1:

Inicialice un nuevo contenedor con el elemento más grande de X o con los dos elementos más grandes de Y, según cuál sea mayor. Tenga en cuenta que, en ambos casos, la suma inicial de los elementos del contenedor es menor que 1.
Llena el nuevo contenedor con artículos de la letra Z en orden creciente de valor.
Repita el proceso hasta que XUY o Z estén vacíos.

Fase 2:

Si XUY está vacío, llene los contenedores con artículos de Z mediante la regla simple de ajuste siguiente.
Si Z está vacío, empaque los elementos restantes en X de dos en dos, y los restantes en Y de tres en tres.

En el ejemplo anterior, que muestra la precisión de BDF, los conjuntos son: ${\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\\{|X|=1\}~&~\{\cdots |Y|=6k\cdots \}~&~\{\cdots |Z|=6k\cdots \}\end{aligned}}$ TCF alcanza el resultado óptimo, ya que inicializa todo $3k$ coloca contenedores con pares de artículos de Y y los llena con pares de artículos de Z.

Para cualquier instancia I , denotemos por $\mathrm {OPT} (I)$ el número de contenedores en la solución óptima, y por $\mathrm {TCF} (I)$ el número de contenedores llenos en el algoritmo de llenado de tres clases. $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ .

El factor 3/4 es ajustado para TCF. Considere el siguiente caso (donde $\epsilon >0$ es suficientemente pequeño):

${\begin{aligned}{\tfrac {1}{2}}-6k\epsilon ,{\tfrac {1}{2}}-6k\epsilon ,~&~{\tfrac {1}{3}}-\epsilon ,\ldots ,{\tfrac {1}{3}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 12k~{\text{units}}\cdots \}~&~\{\cdots 12k~{\text{units}}\cdots \}\end{aligned}}$

TCF inicializa el primer contenedor con los dos elementos más grandes y lo llena con los $12k$ artículos más pequeños. Luego, los restantes $12k$ Los artículos solo pueden cubrir los contenedores en grupos de cuatro, por lo que en total $3k+1$ Los contenedores están llenos. Pero en OPT uno puede llenarlos. $4k$ contenedores, cada uno de los cuales contiene 3 artículos de tamaño mediano y 3 artículos pequeños.

Esquemas de aproximación en tiempo polinomial

Csirik, Johnson y Kenyon ^{[ 3 ]} presentan un PTAS asintótico. Es un algoritmo que, para cada ε >0, llena al menos $(1-5\varepsilon )\cdot \mathrm {OPT} (I)-4$ contenedores si la suma de todos los artículos es mayor que $13B/\epsilon ^{3}$ y al menos $(1-2\varepsilon )\cdot \mathrm {OPT} (I)-1$ De lo contrario, funciona a tiempo. $O(n^{1/\varepsilon ^{2}})$ . El algoritmo resuelve una variante del programa lineal de configuración , con $n^{1/\varepsilon ^{2}}$ variables y $1+1/\varepsilon ^{2}$ restricciones. Este algoritmo solo es interesante teóricamente, ya que para obtener una aproximación mejor que 3/4, debemos tomar $\varepsilon <1/20$ y entonces el número de variables es mayor que $n^{400}$ .

También presentan algoritmos para la versión en línea del problema. En el entorno en línea, no es posible obtener un factor de aproximación asintótica en el peor de los casos mejor que 1/2. Sin embargo, existen algoritmos que funcionan bien en el caso promedio.

Jansen y Solis-Oba ^{[ 4 ]} presentan un FPTAS asintótico. Es un algoritmo que, para cada ε >0, llena al menos $(1-\varepsilon )\cdot \mathrm {OPT} (I)-1$ contenedores si la suma de todos los artículos es mayor que $13B/\epsilon ^{3}$ (si la suma de los elementos es menor que eso, entonces el óptimo es como máximo $13/\epsilon ^{3}\in O(1/\epsilon ^{3})$ De todos modos). Corre a tiempo $O\left({\frac {1}{\epsilon ^{5}}}\cdot \ln {\frac {n}{\varepsilon }}\cdot \max {(n^{2},{\frac {1}{\varepsilon }}\ln \ln {\frac {1}{\varepsilon ^{3}}})}+{\frac {1}{\varepsilon ^{4}}}{\mathcal {T_{M}}}({\frac {1}{\varepsilon ^{2}}})\right)$ , dónde ${\mathcal {T_{M}}}(n)$ es la complejidad temporal del mejor algoritmo disponible para la inversión de matrices (actualmente, alrededor de $O(n^{2.38})$ ). Este algoritmo se vuelve mejor que la aproximación 3/4 ya cuando $\varepsilon <1/4$ y en este caso las constantes son razonables, aproximadamente $2^{10}n^{2}+2^{18}$ .

Rendimiento con tamaños de artículos divisibles

Un caso especial importante de cobertura de contenedores es cuando los tamaños de los elementos forman una secuencia divisible (también llamada factorizada ). Un caso especial de tamaños de elementos divisibles se da en la asignación de memoria en sistemas informáticos, donde los tamaños de los elementos son todos potencias de 2. Si los tamaños de los elementos son divisibles, entonces algunos de los algoritmos heurísticos para la cobertura de contenedores encuentran una solución óptima. ^{[ 5 ]}^{: Sec.5}

Problemas relacionados

En el problema de asignación equitativa de artículos , hay diferentes personas, cada una de las cuales atribuye un valor distinto a cada artículo. El objetivo es asignar a cada persona un contenedor lleno de artículos, de manera que el valor de cada contenedor sea al menos una constante determinada, y que la mayor cantidad de personas posible reciba un contenedor. Muchas técnicas de cobertura de contenedores también se utilizan en este problema.

Implementaciones

Python: El paquete prtpy contiene una implementación de los algoritmos de Csirik-Frenk-Labbe-Zhang .

Referencias

1 2 Assmann, S. F ; Johnson, D. S ; Kleitman, D. J ; Leung, JY-T (1984-12-01). "Sobre una versión dual del problema de empaquetamiento de contenedores unidimensional". Journal of Algorithms . 5 (4): 502– 525. doi : 10.1016/0196-6774(84)90004-X . ISSN 0196-6774 .
1 2 3 Csirik, János; JBG Frenk y M. Labbé y S. Zhang (1999-01-01). "Dos algoritmos simples para la cobertura de contenedores" . Acta Cybernetica . 14 (1): 13– 25. ISSN 2676-993X .
1 2 Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Mejores algoritmos de aproximación para la cobertura de contenedores" . Actas del Duodécimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos . SODA '01. Washington, DC, EE. UU.: Society for Industrial and Applied Mathematics: 557–566 . ISBN 978-0-89871-490-6.
1 2 Jansen, Klaus; Solis-Oba, Roberto (2003). "Un esquema de aproximación asintótica totalmente polinomial para la cobertura de contenedores". Theoretical Computer Science . 306 ( 1– 3): 543– 551. doi : 10.1016/S0304-3975(03)00363-3 . MR 2000192 .
↑ Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de artículos divisibles" . Journal of Complexity . 3 (4): 406– 428. doi : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .

[:0-1] 1 2 Assmann, S. F ; Johnson, D. S ; Kleitman, D. J ; Leung, JY-T (1984-12-01). "Sobre una versión dual del problema de empaquetamiento de contenedores unidimensional". Journal of Algorithms . 5 (4): 502– 525. doi : 10.1016/0196-6774(84)90004-X . ISSN 0196-6774 .

[:1-2] 1 2 3 Csirik, János; JBG Frenk y M. Labbé y S. Zhang (1999-01-01). "Dos algoritmos simples para la cobertura de contenedores" . Acta Cybernetica . 14 (1): 13– 25. ISSN 2676-993X .

[:2-3] 1 2 Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Mejores algoritmos de aproximación para la cobertura de contenedores" . Actas del Duodécimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos . SODA '01. Washington, DC, EE. UU.: Society for Industrial and Applied Mathematics: 557–566 . ISBN 978-0-89871-490-6.

[:3-4] 1 2 Jansen, Klaus; Solis-Oba, Roberto (2003). "Un esquema de aproximación asintótica totalmente polinomial para la cobertura de contenedores". Theoretical Computer Science . 306 ( 1– 3): 543– 551. doi : 10.1016/S0304-3975(03)00363-3 . MR 2000192 .

[:02-5] Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Empaquetado de contenedores con tamaños de artículos divisibles" . Journal of Complexity . 3 (4): 406– 428. doi : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .