Partición numérica equilibrada

La partición numérica balanceada es una variante de la partición numérica multivariada en la que existen restricciones sobre la cantidad de elementos asignados a cada conjunto. La entrada al problema es un conjunto de n elementos de diferentes tamaños y dos enteros m y k . La salida es una partición de los elementos en m subconjuntos, de manera que la cantidad de elementos en cada subconjunto sea como máximo k . Con sujeción a esto, se requiere que las sumas de tamaños en los m subconjuntos sean lo más similares posible.

Un ejemplo de aplicación es la programación de máquinas idénticas, donde cada máquina tiene una cola de trabajos que puede contener como máximo k trabajos. ^{[ 1 ]} El problema también tiene aplicaciones en la fabricación de chips VLSI y en la asignación de herramientas a máquinas en sistemas de fabricación flexible . ^{[ 2 ]}

En la notación estándar de tres campos para problemas de programación óptima de trabajos , el problema de minimizar la suma más grande a veces se denota por " P | # ≤ k | C _max ". El campo central " # ≤ k " denota que el número de trabajos en cada máquina debe ser como máximo k . Esto contrasta con la versión sin restricciones, que se denota por " $P\parallel C_{\max }$ ". ^{[ 3 ]}

Partición equilibrada bidireccional

Un caso especial común, denominado partición equilibrada bidireccional, se da cuando se requieren dos subconjuntos ( m = 2). Estos dos subconjuntos deben contener elementos de piso ( n /2) y techo ( n /2). Se trata de una variante del problema de partición . Es NP-difícil determinar si existe una partición en la que las sumas de los dos subconjuntos sean iguales; véase ^{[ 4 ]} problema [SP12]. Existen numerosos algoritmos que buscan encontrar una partición equilibrada en la que la suma sea lo más cercana posible a la igualdad.

Coffman, Frederickson y Lueker ^{[ 5 ]} presentan una versión restringida del algoritmo LPT (llamada RLPT), en la que las entradas se asignan en pares. Cuando las entradas son variables aleatorias distribuidas uniformemente, la suma máxima esperada de RLPT es exactamente ${\frac {n}{4}}+{\frac {1}{2n+2}}$ . La diferencia de trabajo esperada (diferencia entre la suma más grande y la más pequeña) es $\Theta (1/n)$ . ^{[ 2 ]}
Lueker ^{[ 6 ]} presenta una variante del algoritmo LDM (llamado método de diferenciación por pares (PDM)). Su diferencia de trabajo esperada es $\Theta (1/n)$ .
Tsai ^{[ 2 ]} presenta un algoritmo llamado Diferencia Máxima Restringida (RLD). Su diferencia de trabajo es $O(\log n/n^{2})$ casi con seguridad .
Yakir ^{[ 7 ]} presenta una variante balanceada del algoritmo LDM para m = 2, llamada BLDM. Su diferencia de trabajo esperada es $n^{-\Theta (\log n)}$ .
Mertens ^{[ 8 ]} presenta un algoritmo completo para particionamiento bidireccional equilibrado en cualquier momento. Combina el algoritmo BLDM con el algoritmo completo de Karmarkar-Karp.

Partición de tripletes equilibrada

Otro caso especial, denominado partición de 3 elementos, se da cuando el número de elementos en cada subconjunto debe ser como máximo 3 ( k = 3). Decidir si existe una partición con sumas iguales constituye precisamente el problema de la partición de 3 elementos , conocido por ser fuertemente NP-difícil . Existen algoritmos de aproximación que buscan encontrar una partición cuya suma sea lo más cercana posible a la igualdad.

Kellerer y Woeginger ^{[ 9 ]} adaptan el algoritmo LPT a la partición de tripletas (donde hay como máximo 3* m elementos, y cada subconjunto debe contener como máximo 3 elementos). Su algoritmo se llama LPT modificado o MLPT . Ordena los elementos de mayor a menor, y coloca cada elemento a su vez en el contenedor con la suma más pequeña entre aquellos contenedores que contienen menos de 3 elementos. Demuestran que el algoritmo MLPT alcanza como máximo ${\frac {4m-1}{3m}}$ de la suma máxima mínima , que es la misma razón de aproximación que alcanza LPT para el problema sin restricciones. La cota es ajustada para MLPT.
Chen, He y Lin ^{[ 10 ]} muestran que, para el mismo problema, MLPT alcanza al menos ${\frac {3m-1}{4m-2}}$ de la suma mínima máxima , que es de nuevo la misma proporción que alcanza LPT para el problema sin restricciones.
Kellerer y Kotov ^{[ 11 ]} presentan un algoritmo diferente (para el caso con exactamente 3* m elementos), que alcanza como máximo $7/6$ de la suma mínima más grande .

Particionamiento equilibrado con cardinalidades mayores

Un caso más general, llamado k -particionamiento , ^{[ 12 ]} es cuando el número de elementos en cada subconjunto debe ser como máximo k , donde k puede ser cualquier entero positivo.

Babel, Kellerer y Kotov ^{[ 12 ]} estudian una variante en la que hay k × m elementos (para algún entero k ), y cada uno de los m conjuntos debe contener exactamente k elementos. Presentan varios algoritmos heurísticos para aproximar la suma mínima más grande :
- Algoritmo de plegado : óptimo para m = 2 y, en general, tiene una relación de aproximación ajustada. $2-{\frac {1}{m}}$ .
- Algoritmo de intercambio : relación de aproximación ajustada $2-{\frac {2}{m+1}}$ Se desconoce si su ejecución es en tiempo polinomial.
- Algoritmo primal-dual (una combinación de LPT y MultiFit ): relación de aproximación como máximo $4/3$ . Es ajustado para k = 4 cuando m es suficientemente grande; el límite inferior preciso es ${\frac {4m}{3m+1}}$ ). ^{[ 12 ]}^{: Teorema 11}
- También se conjetura que Modified-LPT tiene una razón de aproximación ${\frac {4m-1}{3m}}$ Actualmente, se sabe que esta conjetura es cierta solo para k = 3. ^{[ 9 ]} Para k > 3, se sabe que su razón de aproximación es como máximo 2. ^{[ 3 ]}
Michiels, Korst, Aarts, van Leeuwen ^{[ 13 ]} y Spieksma ^{[ 14 ]} estudian una variante en la que cada uno de los m conjuntos debe contener elementos techo( n / m ) o piso( n / m ) (de modo que k = techo( n / m )). Extienden el Balanced-LDM (BLDM) de m = 2 a m general . El algoritmo generalizado se ejecuta en tiempo $O(n\log n)$ Demuestran que su razón de aproximación para la suma máxima mínima es exactamente 4/3 para k = 3, 19/12 para k = 4, 103/60 para k = 5, 643/360 para k = 6 y 4603/2520 para k = 7. Las razones se encontraron resolviendo un programa lineal entero mixto . En general (para cualquier k ), la razón de aproximación es al menos $2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}$ y como máximo $2-{\frac {1}{k-1}}$ Los resultados exactos de MILP para 3, 4, 5, 6 y 7 corresponden al límite inferior. Para k > 7, no se conocen resultados exactos, pero la diferencia entre el límite inferior y el superior es menor que el 0,3 %. Cuando el parámetro es el número de subconjuntos ( m ), la razón de aproximación es exactamente $2-{\frac {1}{m}}$ .
Zhang, Mouratidis y Pang ^{[ 1 ]} demuestran que BLDM puede generar particiones con una alta diferencia de trabajo (diferencia entre la suma más alta y la más baja), tanto cuando las entradas se distribuyen uniformemente como cuando su distribución es asimétrica. Proponen dos heurísticas alternativas: LRM reduce la diferencia de trabajo a 1/3 de la diferencia de trabajo de BLDM cuando la distribución es uniforme; Meld reduce la diferencia de trabajo cuando la distribución es asimétrica. Un algoritmo híbrido combina BLDM, LRM y Meld y se adapta dinámicamente a diferentes distribuciones de datos.
Cuando k es fijo, se puede utilizar un PTAS de Hochbaum y Shmoys ^{[ 15 ] para la partición equilibrada.}^{[ 14 ]} Cuando k es parte de la entrada, actualmente no se conoce ningún PTAS. ^{[ 14 ]}
Dell'Amico y Martello ^{[ 3 ]} estudian el problema de minimizar la suma más grande cuando el número de elementos en todos los conjuntos es como máximo k . Demuestran que la relajación de programación lineal de esta variante tiene el mismo valor óptimo que la relajación LP de la variante sin restricciones. La expresión $\max((\sum x_{i})/m,x_{1})$ , donde x _i son las entradas ordenadas de mayor a menor, es una cota inferior para la suma máxima óptima, y su relación en el peor de los casos es 1/2 en ambas variantes. La expresión mejorada $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ tiene una relación de peor caso de 2/3 en la variante sin restricciones y 1/2 en la variante con restricciones. La relación de aproximación de la planificación de lista modificada es 1/2 para la variante sin restricciones, pero es 0 para la variante con restricciones (puede ser arbitrariamente mala). La relación de aproximación del algoritmo LPT modificado es como máximo 2. También muestran que el límite inferior de ^{[ 12 ]} tiene una relación de rendimiento ajustada en el peor caso de 3/4, y que su algoritmo PD tiene una relación de rendimiento ajustada de 4/3 (cuando m es suficientemente grande).
He, Tan, Zhu y Yao ^{[ 16 ]} consideran el problema de maximizar la suma más pequeña. Demuestran que el algoritmo FOLDING tiene una relación de aproximación ajustada. $\max \left({\frac {2}{k}},{\frac {1}{m}}\right)$ Presentan un nuevo algoritmo, HARMONIC1, con una relación en el peor de los casos de al menos $\max \left({\frac {1}{k}},{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)$ Ambos algoritmos son ordinales : dividen los elementos basándose únicamente en el orden entre ellos, en lugar de en sus valores exactos. Demuestran que cualquier algoritmo ordinal tiene como máximo una razón $O(1/\ln {m})$ para maximizar la suma más pequeña. Esto indica que HARMONIC1 es asintóticamente óptimo . Para cualquier k fijo , cualquier algoritmo ordinal tiene una razón como máximo la raíz más pequeña de la ecuación. $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ Cuando k tiende a infinito, este límite superior se aproxima a 0.

Relaciones entre problemas equilibrados y no restringidos

Existen algunas relaciones generales entre las aproximaciones al problema de partición equilibrada y el problema de partición estándar (sin restricciones).

Babel, Kellerer y Kotov ^{[ 12 ]} demuestran que la razón entre el óptimo sin restricciones y el óptimo con restricciones es como máximo $2-{\frac {2}{m}}$ y es ajustado.
Kellerer y Kotov ^{[ 11 ]} demuestran que toda heurística para partición equilibrada con capacidad k y razón de aproximación r (para la suma máxima mínima) puede emplearse para obtener una heurística para partición sin restricciones con razón de aproximación $\max \left(r,{\frac {k+2}{k+1}}-{\frac {1}{m(k+1)}}\right)$ . En particular, su $7/6$ El algoritmo de aproximación para la partición de tripletes ( k = 3) se puede utilizar para obtener una heurística para la partición sin restricciones con una relación de aproximación. $\max \left({\frac {7}{6}},{\frac {5}{4}}-{\frac {1}{4m}}\right)$ .

diferentes restricciones de cardinalidad

Las restricciones de cardinalidad se pueden generalizar permitiendo una restricción diferente en cada subconjunto. Esta variante se introduce en la sección de "problemas abiertos" de ^{[ 12 ]} , quienes denominan al problema de partición k _i . He, Tan, Zhu y Yao ^{[ 16 ]} presentan un algoritmo llamado HARMONIC2 para maximizar la suma más pequeña con diferentes restricciones de cardinalidad. Demuestran que su razón en el peor caso es al menos $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ .

Restricciones de cardinalidad categorizadas

Otra generalización de las restricciones de cardinalidad es la siguiente: Los elementos de entrada se dividen en k categorías. Para cada categoría h , existe una restricción de capacidad k _h . Cada uno de los m subconjuntos puede contener como máximo k _h elementos de la categoría h . En otras palabras: todos los m subconjuntos deben ser conjuntos independientes de un matroide de partición particular . Se han estudiado dos casos especiales de este problema.

Particionamiento del núcleo

En el problema de partición equilibrada de núcleos , m elementos predefinidos son núcleos , y cada uno de los m subconjuntos debe contener un único núcleo (y un número ilimitado de elementos que no son núcleos). Aquí, hay dos categorías: la categoría de núcleos con capacidad 1, y la categoría de elementos que no son núcleos con capacidad ilimitada.

Chen, He y Yao ^{[ 17 ]} demuestran que el problema es NP-difícil incluso para k = 3 (para k = 2 se puede resolver eficientemente encontrando un emparejamiento de peso máximo ). Luego presentan un algoritmo llamado Kernel-LPT (KLPT): asigna un kernel a cada subconjunto y luego ejecuta el algoritmo LPT modificado (coloca cada elemento en el subconjunto con la suma más pequeña entre aquellos que tienen menos de k elementos). Demuestran que, con k = 3, KLPT tiene una razón de aproximación ${\frac {4m-1}{3m}}$ para la suma más grande mínima . ^{[ 17 ]}^{: 3} Sin embargo, Chen, He y Lin ^{[ 10 ]}^{: 2} afirman que su razón de aproximación ajustada es ${\frac {3m-1}{2m}}$ para la suma mínima más grande, y ${\frac {2m-1}{3m-2}}$ para la suma mínima máxima.

Particionamiento de uno por categoría

En otra variante de este problema, hay algunas k categorías de tamaño m , y cada subconjunto debe contener exactamente un elemento de cada categoría. Es decir, k _h = 1 para cada categoría h .

Wu y Yao ^{[ 18 ]}^{[ 19 ]} presentaron el algoritmo LPT por capas , una variante del algoritmo LPT . Demuestran que su razón de aproximación es $2-{\frac {1}{m}}$ para minimizar la suma más grande; ${\frac {1}{m}}$ para maximizar la suma más pequeña en el caso general; y en algunos casos especiales, se puede mejorar a ${\frac {m}{2m-1}}$ para k general y ${\frac {m-1}{2m-3}}$ para k = 3.
Li y Li ^{[ 20 ]} presentaron diferentes algoritmos para el mismo problema. Para minimizar la suma más grande, presentan un EPTAS para k constante y un FPTAS para m constante . Para maximizar la suma más pequeña, presentan un algoritmo de aproximación 1/( k − 1) para el caso general y un EPTAS para k constante . También estudian un objetivo más general: minimizar la norma lp del vector de sumas. Demuestran que el algoritmo Layered-LPT es un algoritmo de aproximación 2 para todas las normas.
Dell'Olmo, Hansen, Pallottino y Storchi ^{[ 21 ]} estudian 32 objetivos diferentes para este problema. Para cada uno de los cuatro operadores max, min, sum, diff, se puede aplicar un operador a los k elementos dentro de cada subconjunto, y luego se puede aplicar un operador a los m resultados para los diferentes subconjuntos. Cada uno de estos 16 objetivos puede maximizarse o minimizarse, para un total de 32. Muestran que 21 de estos problemas pueden resolverse en tiempo lineal; 7 requieren algoritmos más complejos, pero aún de tiempo polinomial; 3 son NP-difíciles: maximizar (min, sum), minimizar (max, sum) y minimizar (diff, sum). Dejaron abierto el estado de minimizar (diff, diff).

Véase también

La partición numérica restringida por matroides es una generalización en la que se proporciona un matroide fijo como parámetro, y cada uno de los m subconjuntos debe ser un conjunto independiente o una base de este matroide.

Las restricciones de cardinalidad son casos especiales de restricciones de matroides en los que el matroide es un matroide uniforme .
Las restricciones de cardinalidad categorizadas son un caso especial en el que el matroide es un matroide de partición .

Referencias

1 2 Zhang, Jilian; Mouratidis, Kyriakos; Pang, HweeHwa (2011-06-28). "Algoritmos heurísticos para la partición numérica multidireccional equilibrada" . Vigésimo segunda Conferencia Internacional Conjunta sobre Inteligencia Artificial .
1 2 3 Tsai, Li-Hui (1992-02-01). "Análisis asintótico de un algoritmo para la planificación equilibrada de procesadores paralelos" . SIAM Journal on Computing . 21 (1): 59– 64. doi : 10.1137/0221007 . ISSN 0097-5397 .
1 2 3 Dell'Amico, Mauro; Martello, Silvano (2001). "Límites para el problema P∥Cmax con restricción de cardinalidad" . Journal of Scheduling . 4 (3): 123– 138. doi : 10.1002/jos.68 . hdl : 11380/15976 . ISSN 1099-1425 .
↑ Garey, Michael; Johnson, David (1979). Computadoras e intratabilidad; una guía a la teoría de la NP-completitud . págs. 96–105 . ISBN 978-0-7167-1045-5.
↑ Coffman, EG; Frederickson, GN; Lueker, GS (1984-05-01). "Una nota sobre los tiempos de finalización esperados para secuencias de tareas independientes de mayor a menor en dos procesadores" . Mathematics of Operations Research . 9 (2): 260– 266. doi : 10.1287/moor.9.2.260 . ISSN 0364-765X .
↑ Lueker, George S (1987-12-01). "Una nota sobre el comportamiento en el caso promedio de un método de diferenciación simple para la partición" . Operations Research Letters . 6 (6): 285– 287. doi : 10.1016/0167-6377(87)90044-7 . ISSN 0167-6377 .
↑ Yakir, Benjamin (1996-02-01). "El algoritmo de diferenciación LDM para la partición: una prueba de una conjetura de Karmarkar y Karp" . Matemáticas de la investigación operativa . 21 (1): 85– 99. doi : 10.1287/moor.21.1.85 . ISSN 0364-765X .
↑ Mertens, Stephan (1999-03-11). "Un algoritmo completo para cualquier momento para la partición de números balanceada". arXiv : cs/9903011 .
1 2 Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "Una cota ajustada para la 3-partición" . Matemáticas Aplicadas Discretas . 45 (3): 249– 259. doi : 10.1016/0166-218X(93)90013-E . ISSN 0166-218X .
1 2 Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "Problemas de partición en 3 para maximizar la carga mínima" . Journal of Combinatorial Optimization . 6 (1): 67– 80. doi : 10.1023/A:1013370208101 . ISSN 1573-2886 . S2CID 9053629 .
1 2 Kellerer, Hans; Kotov, Vladimir (1999-02-01). "Un algoritmo de aproximación 7/6 para la partición 3 y su aplicación a la planificación de multiprocesadores" . INFOR: Information Systems and Operational Research . 37 (1): 48– 56. doi : 10.1080/03155986.1999.11732368 . ISSN 0315-5986 .
1 2 3 4 5 6 Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "El problema de la k -partición" . Métodos matemáticos de investigación operativa . 47 (1): 59– 82. doi : 10.1007/BF01193837 . ISSN 1432-5217 . S2CID 5594197 .
^ Michiels, Wil; Korst, enero; Aarts, Emilio; van Leeuwen, Jan (2003), Ratios de rendimiento para el método de diferenciación aplicado al problema de partición de números equilibrados , Lecture Notes in Computer Science, vol. 2607, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 583–595 , doi : 10.1007/3-540-36494-3_51 , ISBN 978-3-540-00623-7, consultado el 15 de octubre de 2021
1 2 3 Michiels, W.; Aarts, E.; Korst, J.; van Leeuwen, J.; Spieksma, FCR (1 de febrero de 2012). "Prueba de ratios de rendimiento asistida por computadora para el método de diferenciación" . Optimización discreta . 9 (1): 1– 16. doi : 10.1016/j.disopt.2011.10.001 . ISSN 1572-5286 .
↑ Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Uso de algoritmos de aproximación dual para problemas de programación: resultados teóricos y prácticos" . Journal of the ACM . 34 (1): 144– 162. doi : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .
1 2 He, Yong; Tan, Zhiyi; Zhu, Jing; Yao, Enyu (2003-11-01). "Problemas de κ-partición para maximizar la carga mínima" . Computers & Mathematics with Applications . 46 (10): 1671– 1681. doi : 10.1016/S0898-1221(03)90201-X . ISSN 0898-1221 .
1 2 Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic" . Computing . 57 (3): 255– 271. doi : 10.1007/bf02247409 . ISSN 0010-485X . S2CID 21935917 .
↑ Wu, Biao; Yao, Enyue (2007-04-20). "Problemas de m-particionamiento con restricción de matroide de partición". Theoretical Computer Science . 374 (1): 41– 48. doi : 10.1016/j.tcs.2006.11.016 . ISSN 0304-3975 .
↑ Wu, Biao; Yao, En-yu (2008-03-01). "Límites inferiores y algoritmo LPT modificado para problemas de m-partición con restricción de matroide de partición" . Matemáticas Aplicadas - Revista de Universidades Chinas . 23 (1): 1– 8. doi : 10.1007/s11766-008-0101-8 . ISSN 1993-0445 . S2CID 16565038 .
↑ Li, Weidong; Li, Jianping (2013-04-06). "Algoritmos de aproximación para problemas de partición $$m$$ con restricción de matroide de partición" . Optimization Letters . 8 (3): 1093– 1099. doi : 10.1007/s11590-013-0637-2 . ISSN 1862-4472 . S2CID 3385030 .
^ Dell'Olmo, Paolo; Hansen, Pedro; Palotino, Stefano; Storchi, Giovanni (1 de septiembre de 2005). "Sobre problemas de partición k uniforme". Matemática Aplicada Discreta . 150 (1): 121– 139. doi : 10.1016/j.dam.2005.02.013 . ISSN 0166-218X .

[:8-1] 1 2 Zhang, Jilian; Mouratidis, Kyriakos; Pang, HweeHwa (2011-06-28). "Algoritmos heurísticos para la partición numérica multidireccional equilibrada" . Vigésimo segunda Conferencia Internacional Conjunta sobre Inteligencia Artificial .

[:52-2] 1 2 3 Tsai, Li-Hui (1992-02-01). "Análisis asintótico de un algoritmo para la planificación equilibrada de procesadores paralelos" . SIAM Journal on Computing . 21 (1): 59– 64. doi : 10.1137/0221007 . ISSN 0097-5397 .

[:9-3] 1 2 3 Dell'Amico, Mauro; Martello, Silvano (2001). "Límites para el problema P∥Cmax con restricción de cardinalidad" . Journal of Scheduling . 4 (3): 123– 138. doi : 10.1002/jos.68 . hdl : 11380/15976 . ISSN 1099-1425 .

[Garey_&_Johnson-4] Garey, Michael; Johnson, David (1979). Computadoras e intratabilidad; una guía a la teoría de la NP-completitud . págs. 96–105 . ISBN 978-0-7167-1045-5.

[5] Coffman, EG; Frederickson, GN; Lueker, GS (1984-05-01). "Una nota sobre los tiempos de finalización esperados para secuencias de tareas independientes de mayor a menor en dos procesadores" . Mathematics of Operations Research . 9 (2): 260– 266. doi : 10.1287/moor.9.2.260 . ISSN 0364-765X .

[6] Lueker, George S (1987-12-01). "Una nota sobre el comportamiento en el caso promedio de un método de diferenciación simple para la partición" . Operations Research Letters . 6 (6): 285– 287. doi : 10.1016/0167-6377(87)90044-7 . ISSN 0167-6377 .

[:1-7] Yakir, Benjamin (1996-02-01). "El algoritmo de diferenciación LDM para la partición: una prueba de una conjetura de Karmarkar y Karp" . Matemáticas de la investigación operativa . 21 (1): 85– 99. doi : 10.1287/moor.21.1.85 . ISSN 0364-765X .

[8] Mertens, Stephan (1999-03-11). "Un algoritmo completo para cualquier momento para la partición de números balanceada". arXiv : cs/9903011 .

[:0-9] 1 2 Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "Una cota ajustada para la 3-partición" . Matemáticas Aplicadas Discretas . 45 (3): 249– 259. doi : 10.1016/0166-218X(93)90013-E . ISSN 0166-218X .

[:2-10] 1 2 Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "Problemas de partición en 3 para maximizar la carga mínima" . Journal of Combinatorial Optimization . 6 (1): 67– 80. doi : 10.1023/A:1013370208101 . ISSN 1573-2886 . S2CID 9053629 .

[:6-11] 1 2 Kellerer, Hans; Kotov, Vladimir (1999-02-01). "Un algoritmo de aproximación 7/6 para la partición 3 y su aplicación a la planificación de multiprocesadores" . INFOR: Information Systems and Operational Research . 37 (1): 48– 56. doi : 10.1080/03155986.1999.11732368 . ISSN 0315-5986 .

[:4-12] 1 2 3 4 5 6 Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "El problema de la k -partición" . Métodos matemáticos de investigación operativa . 47 (1): 59– 82. doi : 10.1007/BF01193837 . ISSN 1432-5217 . S2CID 5594197 .

[13] Michiels, Wil; Korst, enero; Aarts, Emilio; van Leeuwen, Jan (2003), Ratios de rendimiento para el método de diferenciación aplicado al problema de partición de números equilibrados , Lecture Notes in Computer Science, vol. 2607, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 583–595 , doi : 10.1007/3-540-36494-3_51 , ISBN 978-3-540-00623-7, consultado el 15 de octubre de 2021

[:7-14] 1 2 3 Michiels, W.; Aarts, E.; Korst, J.; van Leeuwen, J.; Spieksma, FCR (1 de febrero de 2012). "Prueba de ratios de rendimiento asistida por computadora para el método de diferenciación" . Optimización discreta . 9 (1): 1– 16. doi : 10.1016/j.disopt.2011.10.001 . ISSN 1572-5286 .

[:02-15] Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Uso de algoritmos de aproximación dual para problemas de programación: resultados teóricos y prácticos" . Journal of the ACM . 34 (1): 144– 162. doi : 10.1145/7531.7535 . ISSN 0004-5411 . S2CID 9739129 .

[:10-16] 1 2 He, Yong; Tan, Zhiyi; Zhu, Jing; Yao, Enyu (2003-11-01). "Problemas de κ-partición para maximizar la carga mínima" . Computers & Mathematics with Applications . 46 (10): 1671– 1681. doi : 10.1016/S0898-1221(03)90201-X . ISSN 0898-1221 .

[:3-17] 1 2 Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic" . Computing . 57 (3): 255– 271. doi : 10.1007/bf02247409 . ISSN 0010-485X . S2CID 21935917 .

[18] Wu, Biao; Yao, Enyue (2007-04-20). "Problemas de m-particionamiento con restricción de matroide de partición". Theoretical Computer Science . 374 (1): 41– 48. doi : 10.1016/j.tcs.2006.11.016 . ISSN 0304-3975 .

[19] Wu, Biao; Yao, En-yu (2008-03-01). "Límites inferiores y algoritmo LPT modificado para problemas de m-partición con restricción de matroide de partición" . Matemáticas Aplicadas - Revista de Universidades Chinas . 23 (1): 1– 8. doi : 10.1007/s11766-008-0101-8 . ISSN 1993-0445 . S2CID 16565038 .

[20] Li, Weidong; Li, Jianping (2013-04-06). "Algoritmos de aproximación para problemas de partición $$m$$ con restricción de matroide de partición" . Optimization Letters . 8 (3): 1093– 1099. doi : 10.1007/s11590-013-0637-2 . ISSN 1862-4472 . S2CID 3385030 .

[21] Dell'Olmo, Paolo; Hansen, Pedro; Palotino, Stefano; Storchi, Giovanni (1 de septiembre de 2005). "Sobre problemas de partición k uniforme". Matemática Aplicada Discreta . 150 (1): 121– 139. doi : 10.1016/j.dam.2005.02.013 . ISSN 0166-218X .

[ 4 ]

[ 5 ]

[ 6 ]

[ 8 ]

[ 13 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]