Partición de números multidireccional

En informática , la partición de números multidireccional es el problema de particionar un multiconjunto de números en un número fijo de subconjuntos, de modo que las sumas de los subconjuntos sean lo más similares posible. Fue presentado por primera vez por Ronald Graham en 1969 en el contexto del problema de programación de máquinas idénticas . ^{[1] : sec.5} El problema está parametrizado por un entero positivo k , y se denomina partición de números de k vías . ^[2] La entrada al problema es un multiconjunto S de números (normalmente enteros), cuya suma es k*T .

El problema de decisión asociado consiste en decidir si S se puede dividir en k subconjuntos de modo que la suma de cada subconjunto sea exactamente T. También existe un problema de optimización : encontrar una partición de S en k subconjuntos, de modo que las k sumas sean "lo más cercanas posible". El objetivo exacto de optimización se puede definir de varias maneras:

• Minimizar la diferencia entre la suma mayor y la suma menor. Este objetivo es común en artículos sobre particionamiento de números multidireccional, así como en artículos que se originan en aplicaciones de física. ^[2]
• Minimizar la suma más grande. Este objetivo es equivalente a un objetivo de programación de máquinas idénticas . Hay k procesadores idénticos y cada número en S representa el tiempo necesario para completar un trabajo de un solo procesador. El objetivo es dividir los trabajos entre los procesadores de modo que se minimice el tiempo de finalización del último trabajo.
• Maximizar la suma más pequeña. Este objetivo corresponde a la aplicación de la asignación justa de elementos , particularmente la participación maximin . También aparece en problemas de manipulación de votaciones, ^[3] y en la secuenciación de acciones de mantenimiento para motores de aeronaves de turbina de gas modulares. ^{[4] [5]} Supongamos que hay algunos k motores, que deben mantenerse en funcionamiento durante el mayor tiempo posible. Un motor necesita una cierta parte crítica para funcionar. Hay un conjunto S de partes, cada una de las cuales tiene una vida útil diferente. El objetivo es asignar las partes a los motores, de modo que la vida útil del motor más corta sea lo más grande posible.

Estas tres funciones objetivo son equivalentes cuando k = 2, pero son todas diferentes cuando k ≥3. ^{[6] [7]}

Todos estos problemas son NP-hard , ^[8] pero hay varios algoritmos que los resuelven eficientemente en muchos casos.

Algunos problemas estrechamente relacionados son:

• El problema de la partición : un caso especial de partición de números multidireccional en el que el número de subconjuntos es 2.
• El problema de las tres particiones es un problema diferente y más difícil, en el que el número de subconjuntos no se considera un parámetro fijo, sino que está determinado por la entrada (el número de conjuntos es el número de números enteros dividido por 3).
• Problema de empaquetamiento de bins : un problema dual en el que la suma total de cada subconjunto está acotada, pero k es flexible; el objetivo es encontrar una partición con el k más pequeño posible . Los objetivos de optimización están estrechamente relacionados: el número óptimo de bins de tamaño d es como máximo k , si y solo si el tamaño óptimo de un subconjunto más grande en una partición k es como máximo d . ^[9]
• El problema de programación de máquinas uniformes : un problema más general en el que diferentes procesadores pueden tener diferentes velocidades.

Algoritmos de aproximación

Existen diversos algoritmos que obtienen una aproximación garantizada de la solución óptima en tiempo polinómico. Existen distintos algoritmos de aproximación para distintos objetivos.

Minimizar la suma más grande

En este contexto, la razón de aproximación es la suma más grande de la solución que devuelve el algoritmo, dividida por la suma más grande de la solución óptima (la razón es mayor que 1). La mayoría de los algoritmos que se describen a continuación se desarrollaron para la programación de máquinas idénticas .

• La partición de números voraz (también llamada el Tiempo de procesamiento más grande en la literatura de programación) recorre los números y coloca cada número en el conjunto cuya suma actual es la más pequeña. Si los números no están ordenados, entonces el tiempo de ejecución esy la razón de aproximación es como máximo. Ordenar los números aumenta el tiempo de ejecución ay mejora la razón de aproximación a 7/6 cuando k = 2, yen general. Si los números se distribuyen uniformemente en [0,1], entonces la razón de aproximación es como máximo casi con seguridad , yen expectativa. ${\displaystyle O(n)}$ ${\displaystyle 2-1/k}$ ${\displaystyle O(n\log {n})}$ ${\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}={\frac {4k-1}{3k}}}$ ${\displaystyle 1+O(\log {\log {n}}/n)}$ ${\displaystyle 1+O(1/n)}$
• El método de diferenciación más grande (también llamado algoritmo Karmarkar-Karp ) ordena los números en orden descendente y reemplaza repetidamente los números por sus diferencias. La complejidad en tiempo de ejecución es. En el peor de los casos, su razón de aproximación es similar: como máximo 7/6 para k = 2, y como máximoen general. Sin embargo, en el caso promedio, funciona mucho mejor que el algoritmo voraz: para k = 2, cuando los números se distribuyen uniformemente en [0,1], su razón de aproximación es como máximoen expectativa. También funciona mejor en experimentos de simulación. ${\displaystyle O(n\log {n})}$ ${\displaystyle 4/3-1/3k}$ ${\displaystyle 1+1/n^{\Theta (\log {n})}}$
• El algoritmo Multifit utiliza una búsqueda binaria combinada con un algoritmo de empaquetamiento de bins . En el peor de los casos, su makespan es como máximo 8/7 para k = 2, y como máximo 13/11 en general.

Se han desarrollado varios esquemas de aproximación en tiempo polinomial (PTAS):

• Graham ^{[1] : la sección 6} presentó el siguiente algoritmo. Para cualquier entero r>0 , se eligen los r números más grandes en S y se los divide de manera óptima. Luego, se asignan los números restantes de manera arbitraria. Este algoritmo tiene una razón de aproximación y se ejecuta en tiempo . ${\displaystyle 1+{\frac {1-1/k}{1+\lfloor r/k\rfloor }}}$ ${\displaystyle O(2^{r}n\log {n})}$
• Sahni ^[10] presentó un PTAS que alcanza (1+ε)OPT en tiempo . Es un FPTAS si k es fijo. Para k = 2, el tiempo de ejecución mejora a . El algoritmo utiliza una técnica llamada partición de intervalos . ${\displaystyle O(n\cdot (n^{2}/\epsilon )^{k-1})}$ ${\displaystyle O(n^{2}/\epsilon )}$
• Hochbaum y Shmoys ^[9] presentaron los siguientes algoritmos, que funcionan incluso cuando k es parte de la entrada.
  • Para cualquier r > 0, un algoritmo con razón de aproximación como máximo (6/5+2 ^{− r} ) en el tiempo . ${\displaystyle O(n(r+\log {n}))}$
  • Para cualquier r > 0, un algoritmo con razón de aproximación como máximo (7/6+2 ^{− r} ) en el tiempo . ${\displaystyle O(n(rk^{4}+\log {n}))}$
  • Para cualquier ε > 0, un algoritmo con razón de aproximación como máximo (1+ε) en el tiempo . Este es un PTAS . ${\displaystyle O((n/\varepsilon )^{(1/\varepsilon ^{2})})}$

Maximizar la suma más pequeña

La razón de aproximación en este contexto es la suma más pequeña en la solución devuelta por el algoritmo, dividida por la suma más pequeña en la solución óptima (la razón es menor que 1).

• Para la partición de números codiciosos , si los números no están ordenados, entonces la relación de aproximación en el peor de los casos es 1/ k . ^[11] Ordenar los números aumenta la relación de aproximación a 5/6 cuando k = 2 y, en general, es estricta. ^[12] ${\displaystyle {\frac {3k-1}{4k-2}}}$
• Woeginger ^[11] presentó un PTAS que alcanza un factor de aproximación de en el tiempo , donde una constante enorme que es exponencial en el factor de aproximación requerido ε. El algoritmo utiliza el algoritmo de Lenstra para programación lineal entera . ${\displaystyle 1-{\varepsilon }}$ ${\displaystyle O(c_{\varepsilon }n\log {k})}$ ${\displaystyle c_{\varepsilon }}$
• El FPTAS de Sahni ^[10] también trabaja para este objetivo.

Maximizar la suma de productos

Jin ^[13] estudia un problema en el que el objetivo es maximizar la suma, sobre cada conjunto i en 1,..., k , del producto de los números del conjunto i . En una variante más general, cada conjunto i puede tener un peso w _i y el objetivo es maximizar la suma ponderada de los productos. Este problema tiene una solución exacta que se ejecuta en el tiempo O( n ² ).

Un PTAS para funciones objetivas generales

Sea C _i (para i entre 1 y k ) la suma del subconjunto i en una partición dada. En lugar de minimizar la función objetivo max( C _i ), se puede minimizar la función objetivo max( f ( C _i )), donde f es cualquier función fija. De manera similar, se puede minimizar la función objetivo sum( f ( C _i )), o maximizar min(f( C _i )), o maximizar sum( f ( C _i )). Alon, Azar, Woeginger y Yadid ^[14] presentaron PTAS-s generales (generalizando los PTAS-s de Sanhi, Hochbaum y Shmoys, y Woeginger) para estos cuatro problemas. Su algoritmo funciona para cualquier f que satisfaga las dos condiciones siguientes:

1. Una condición de continuidad fuerte llamada Condición F* : para todo ε>0 existe δ>0 tal que, si | y - x |<δ x , entonces |f( y )-f( x )|<ε f ( x ).
2. Convexidad (para los problemas de minimización) o concavidad (para los problemas de maximización).

El tiempo de ejecución de sus PTAS es lineal en n (la cantidad de entradas), pero exponencial en la precisión de aproximación. El PTAS para minimizar suma( f ( C _i )) se basa en algunas observaciones combinatorias:

1. Sea L  := la suma promedio en un único subconjunto (1/ k la suma de todas las entradas). Si alguna entrada x es al menos L , entonces hay una partición óptima en la que una parte contiene solo x . Esto se deduce de la convexidad de f . Por lo tanto, la entrada puede preprocesarse asignando cada una de esas entradas a un único subconjunto. Después de este preprocesamiento, se puede suponer que todas las entradas son menores que L .
2. Existe una partición óptima en la que las sumas de todos los subconjuntos están estrictamente entre L /2 y 2L ( L / 2 < C _i < 2L para todo i en 1,..., k ). En particular, la partición que minimiza la suma de cuadrados C _i ² , entre todas las particiones óptimas, satisface estas desigualdades.

El PTAS utiliza una técnica de redondeo de entrada . Dada la secuencia de entrada S = ( v ₁ ,..., v _n ) y un entero positivo d , la secuencia redondeada S ^# ( d ) se define de la siguiente manera:

• Para cualquier v _j > L/d , la secuencia S ^# ( d ) contiene una entrada v _j ^# que es v _j redondeado al siguiente múltiplo entero de L / d ² . Nótese que v _j ≤ v _j ^# < v _j + L / d ² , y L/d ² < v _j / d , entonces v _j ^# < ( d +1) v _j / d.
• Además, la secuencia S ^# ( d ) contiene algunas entradas iguales a L/d . El número de estas entradas se determina de modo que la suma de todas estas nuevas entradas sea igual a la suma de todas las entradas en S ^# ( d ) que sean como máximo L/d , redondeadas al siguiente múltiplo entero de L/d (por ejemplo, si la suma de todas las entradas "cortas" en S es 51,3 L/d , entonces se agregan 52 nuevas entradas L/d a S ^# ( d )).

En S ^# ( d ), todas las entradas son múltiplos enteros de L / d ² . Además, las dos observaciones anteriores también son válidas para S ^# ( d ):

1. Sea L ^# la suma promedio en un único subconjunto (1/ k la suma de todas las entradas en S ^# ( d )). Por construcción, L ^# es al menos L . Dado que L en sí es un múltiplo entero de L / d ² , el redondeo de las entradas menores que L no puede hacerlas mayores que L . Por lo tanto, todas las entradas en S ^# ( d ) son menores que L , y por lo tanto menores que L ^# .
2. Existe una partición óptima de S ^# ( d ) en la que todas las sumas de los subconjuntos están estrictamente entre L ^# /2 y 2L # ^. Por lo tanto, todos los subconjuntos contienen como máximo 2d elementos (ya que todas las entradas en S ^# ( d ) son al menos L / d ).

Con base en estas observaciones, todas las entradas en S ^# ( d ) son de la forma hL / d ² , donde h es un entero en el rango . Por lo tanto, la entrada puede representarse como un vector entero , donde es el número de hL / d ² entradas en S ^# ( d ). Además, cada subconjunto puede representarse como un vector entero , donde es el número de hL / d ² entradas en el subconjunto. La suma del subconjunto es entonces . Denotemos por , el conjunto de vectores con . Dado que la suma de elementos en tal vector es como máximo 2 d , el número total de estos elementos es menor que , por lo que . ${\displaystyle (d,d+1,\ldots ,d^{2})}$ ${\displaystyle \mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})}$ ${\displaystyle n_{h}}$ ${\displaystyle \mathbf {t} =(t_{d},t_{d+1},\ldots ,t_{d^{2}})}$ ${\displaystyle x_{h}}$ ${\displaystyle C(\mathbf {t} )=\sum _{h=d}^{d^{2}}t_{h}\cdot (hL/d^{2})}$ ${\displaystyle T}$ ${\displaystyle \mathbf {t} }$ ${\displaystyle L^{\#}/2<C(\mathbf {t} )<2L^{\#}}$ ${\displaystyle {(d^{2})}^{2d}=d^{4d}}$ ${\displaystyle |T|\leq d^{4d}}$

Hay dos formas diferentes de encontrar una solución óptima para S ^# ( d ). Una forma utiliza programación dinámica: su tiempo de ejecución es un polinomio cuyo exponente depende de d . La otra forma utiliza el algoritmo de Lenstra para programación lineal entera.

Solución de programación dinámica

Definir como el valor óptimo (mínimo) de la función objetivo suma( f ( C _i )), cuando el vector de entrada es y debe ser dividido en k subconjuntos, entre todas las particiones en las que todas las sumas de los subconjuntos están estrictamente entre L ^# /2 y 2 L ^# . ${\displaystyle VAL(k,\mathbf {n} )}$ ${\displaystyle \mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})}$

Se puede resolver mediante la siguiente relación de recurrencia :

• ${\displaystyle VAL(0,\mathbf {0} )=0}$- ya que su suma objetivo está vacía.
• ${\displaystyle VAL(1,\mathbf {n} )=f(C(\mathbf {n} ))}$si - dado que todas las entradas deben asignarse a un solo subconjunto, entonces su suma es . ${\displaystyle L^{\#}/2<C(\mathbf {n} ))<2L^{\#}}$ ${\displaystyle C(\mathbf {n} )}$
• ${\displaystyle VAL(1,\mathbf {n} )=\infty }$de lo contrario, ya que no consideramos soluciones óptimas fuera de este rango.
• ${\displaystyle VAL(k,\mathbf {n} )=\min _{\mathbf {t} \leq \mathbf {n} ,\mathbf {t} \in T}[f(C(\mathbf {t} ))+VAL(k-1,\mathbf {n} -\mathbf {t} )]}$para todos : verificamos todas las opciones para el k -ésimo subconjunto y lo combinamos con una partición óptima del resto en k -1 subconjuntos. ${\displaystyle k\geq 2}$

Para cada k y n , la relación de recurrencia requiere verificar como máximo vectores. El número total de vectores n a verificar es como máximo , donde n es el número original de entradas. Por lo tanto, el tiempo de ejecución del algoritmo de programación dinámica es . Es lineal en n para cualquier d fijo . ${\displaystyle |T|}$ ${\displaystyle n^{d^{2}}}$ ${\displaystyle O(k\cdot n^{d^{2}}\cdot d^{4d})}$

Solución de programación lineal entera

Para cada vector t en T , introduzca una variable x _t que denote el número de subconjuntos con esta configuración. La minimización de suma( f ( C _i )) se puede lograr resolviendo el siguiente ILP:

• Minimizar ${\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }\cdot f(C(\mathbf {t} ))}$
• sujeto a (el número total de subconjuntos) ${\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }=k}$
• y (el vector total de entradas) ${\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }\cdot \mathbf {t} =\mathbf {n} }$
• y . ${\displaystyle x_{\mathbf {t} }\geq 0}$

El número de variables es como máximo , y el número de ecuaciones es - ambas son constantes independientes de n , k . Por lo tanto, se puede utilizar el algoritmo de Lenstra . Su tiempo de ejecución es exponencial en la dimensión ( ), pero polinomial en la representación binaria de los coeficientes, que están en O(log( n )). La construcción del ILP en sí lleva un tiempo O( n ). ${\displaystyle d^{4d}}$ ${\displaystyle d^{4d}+d^{2}-d+2}$ ${\displaystyle d^{4d}}$

Convertir la solución de la instancia redondeada a la original

Los siguientes lemas relacionan las particiones de la instancia redondeada S ^# ( d ) y la instancia original S .

• Para cada partición de S con sumas C _i , hay una partición de S ^# ( d ) con sumas C _i ^# , donde . ${\displaystyle C_{i}-{\frac {L}{d}}\leq C_{i}^{\#}\leq {\frac {d+1}{d}}C_{i}+{\frac {L}{d}}}$
• Para cada partición de S ^# ( d ) con sumas C _i ^# , hay una partición de S con sumas C _i , donde , y se puede encontrar en el tiempo O( n ). ${\displaystyle {\frac {d}{d+1}}C_{i}^{\#}-2{\frac {L}{d}}\leq C_{i}\leq C_{i}^{\#}+{\frac {L}{d}}}$

Dada una precisión de aproximación deseada ε>0, sea δ>0 la constante correspondiente a ε/3, cuya existencia está garantizada por la condición F*. Sea . Es posible demostrar que la partición convertida de S tiene un costo total de como máximo , por lo que la razón de aproximación es 1+ε. ${\displaystyle d:=\lceil 5/\delta \rceil }$ ${\displaystyle (1+{\frac {\epsilon }{3}})\cdot OPT\leq (1+\epsilon )\cdot OPT}$

Inexistencia de PTAS para algunas funciones objetivas

En contraste con el resultado anterior, si tomamos f( x ) = 2 ^x , o f( x )=( x -1) ² , entonces no existe PTAS para minimizar suma( f ( C _i )) a menos que P=NP . ^{[14] : Sec.4} Nótese que estas f( x ) son convexas, pero no satisfacen la condición F* anterior. La prueba es por reducción del problema de partición .

Algoritmos exactos

Existen algoritmos exactos que siempre encuentran la partición óptima. Dado que el problema es NP-hard, dichos algoritmos pueden requerir un tiempo exponencial en general, pero pueden ser utilizables en la práctica en ciertos casos.

• La partición numérica del tiempo pseudopolinomial requiere una memoria de O ( n ( k − 1) m ^{k − 1} ) , donde m es el número más grande en la entrada. Es práctica solo cuando k = 2, o cuando k = 3 y las entradas son números enteros pequeños. ^[15]
• El algoritmo voraz completo (CGA) considera todas las particiones mediante la construcción de un árbol k - ario . Cada nivel del árbol corresponde a un número de entrada, donde la raíz corresponde al número más grande, el nivel inferior al siguiente número más grande, etc. Cada una de las k ramas corresponde a un conjunto diferente en el que se puede colocar el número actual. Recorrer el árbol en orden de profundidad requiere solo O( n ) espacio, pero podría tomar O( k ⁿ ) tiempo. El tiempo de ejecución se puede mejorar utilizando una heurística voraz: en cada nivel, desarrolle primero la rama en la que se coloca el número actual en el conjunto con la suma más pequeña. Este algoritmo encuentra primero la solución encontrada por la partición de números voraces , pero luego procede a buscar mejores soluciones.
• El algoritmo completo Karmarkar-Karp (CKK) considera todas las particiones mediante la construcción de un árbol de grado . Cada nivel corresponde a un par de k -tuplas, y cada una de las ramas corresponde a una forma diferente de combinar estas k -tuplas. Este algoritmo encuentra primero la solución encontrada por el método de diferenciación más grande , pero luego procede a encontrar mejores soluciones. Para k = 2 y k = 3, CKK se ejecuta sustancialmente más rápido que CGA en instancias aleatorias. La ventaja de CKK sobre CGA es mucho mayor en el último caso (cuando existe una partición igual), y puede ser de varios órdenes de magnitud. En la práctica, con k = 2, los problemas de tamaño arbitrario pueden resolverse con CKK si los números tienen como máximo 12 dígitos significativos ; con k = 3, como máximo 6 dígitos significativos. ^[16] CKK también puede ejecutarse como un algoritmo en cualquier momento : encuentra primero la solución KK y luego encuentra soluciones progresivamente mejores a medida que el tiempo lo permite (posiblemente requiriendo tiempo exponencial para alcanzar la optimalidad, para los peores casos). ^[17] Para k ≥ 4, CKK se vuelve mucho más lento y CGA funciona mejor. ${\displaystyle k!}$ ${\displaystyle k!}$
• Korf, Schreiber y Moffitt presentaron algoritmos híbridos que combinan CKK, CGA y otros métodos del problema de suma de subconjuntos y el problema de empaquetamiento de contenedores para lograr un rendimiento aún mejor. Su artículo de revista de 2018 ^[18] resume trabajos de varios artículos de conferencias anteriores:
  • La partición de números recursiva (RNP) ^[15] utiliza CKK para k = 2, pero para k > 2 divide recursivamente S en subconjuntos y divide k en mitades.
  • Partición de números recursiva híbrida (HRNP). ^[19]
  • Se mejoró la finalización de los contenedores. ^[20]
  • Estrategias de búsqueda mejoradas. ^[21]
  • Algoritmo de pocas máquinas. ^[22]
  • Debilitamiento iterativo en caché (CIW). ^[23]
  • Particionamiento secuencial . ^[24]

Reducción al embalaje en contenedores

El problema del empaquetamiento de contenedores tiene muchos solucionadores rápidos. Se puede utilizar un solucionador BP para encontrar una partición numérica óptima. ^[25] La idea es utilizar la búsqueda binaria para encontrar el makespan óptimo. Para inicializar la búsqueda binaria, necesitamos un límite inferior y un límite superior:

• Algunos límites inferiores del makespan son: (suma S )/ k - el valor promedio por subconjunto, s ₁ - el número más grande en S , y s _k + s _{k+1 - el tamaño de un contenedor en la partición óptima de solo los números} k +1 más grandes .
• Se pueden alcanzar algunos límites superiores ejecutando algoritmos heurísticos, como el algoritmo voraz o KK.

Dado un límite inferior y uno superior, ejecute el solucionador BP con tamaño de bin medio := (inferior+superior)/2.

• Si el resultado contiene más de k contenedores, entonces el makespan óptimo debe ser mayor: configúrelo de menor a mayor y repita.
• Si el resultado contiene como máximo k contenedores, entonces el intervalo de creación óptimo puede ser menor, establecerse en un nivel más alto en el medio y repetirse.

Variantes

En el problema de partición de números balanceados , existen restricciones en la cantidad de elementos que se pueden asignar a cada subconjunto (estas se denominan restricciones de cardinalidad ).

Otra variante es la partición de números multidimensionales . ^[26]

Aplicaciones

Una aplicación del problema de la partición es la manipulación de elecciones . Supongamos que hay tres candidatos (A, B y C). Se debe elegir un único candidato utilizando la regla de votación con veto, es decir, cada votante veta a un único candidato y gana el candidato con menos vetos. Si una coalición quiere asegurarse de que C sea elegido, debe repartir sus vetos entre A y B de modo de maximizar el menor número de vetos que cada uno de ellos obtenga. Si los votos están ponderados, entonces el problema se puede reducir al problema de la partición y, por lo tanto, se puede resolver de manera eficiente utilizando CKK. Para k = 2, lo mismo es cierto para cualquier otra regla de votación que se base en la puntuación. Sin embargo, para k > 2 y otras reglas de votación, se requieren otras técnicas. ^[3]

Implementaciones

• Python: El paquete prtpy contiene código para varios algoritmos de particionamiento de números y empaquetamiento de contenedores.

Referencias

1. Graham, Ron L. (1969-03-01). "Límites en anomalías de tiempo de multiprocesamiento". Revista SIAM de Matemáticas Aplicadas . 17 (2): 416–429. doi :10.1137/0117039. ISSN  0036-1399.
2. Mertens, Stephan (2006), "El problema más fácil y difícil: la partición de números", en Allon Percus; Gabriel Istrate; Cristopher Moore (eds.), Complejidad computacional y física estadística , Oxford University Press US, pág. 125, arXiv : cond-mat/0310317 , Bibcode :2003cond.mat.10317M, ISBN 978-0-19-517737-4
3. Walsh, Toby (11 de julio de 2009). "¿Dónde están los problemas de manipulación realmente difíciles? La transición de fase en la manipulación de la regla de veto" (PDF) . Escrito en Pasadena, California, EE. UU. Actas de la 21.ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . San Francisco, California, EE. UU.: Morgan Kaufmann Publishers Inc., págs. 324–329. Archivado (PDF) desde el original el 10 de julio de 2020. Consultado el 5 de octubre de 2021 .
4. Friesen, DK; Deuermeyer, BL (1981-02-01). "Análisis de soluciones voraces para un problema de secuenciación de piezas de repuesto". Matemáticas de la investigación de operaciones . 6 (1): 74–87. doi :10.1287/moor.6.1.74. ISSN  0364-765X.
5. Deuermeyer, Bryan L.; Friesen, Donald K.; Langston, Michael A. (1 de junio de 1982). "Programación para maximizar el tiempo mínimo de finalización del procesador en un sistema multiprocesador". Revista SIAM sobre métodos algebraicos y discretos . 3 (2): 190–196. doi :10.1137/0603019. ISSN  0196-5212.
6. Korf, Richard Earl (25 de agosto de 2010). "Funciones objetivas para particionamiento de números multidireccional". Tercer simposio anual sobre búsqueda combinatoria . 1 : 71–72. doi : 10.1609/socs.v1i1.18172 . S2CID  45875088.
7. Walter, Rico (1 de enero de 2013). "Comparación de los tiempos mínimos de finalización de dos heurísticas de planificación más largas". Revista centroeuropea de investigación de operaciones . 21 (1): 125–139. doi :10.1007/s10100-011-0217-4. ISSN  1613-9178. S2CID  17222989.
8. Garey, Michael R.; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman and Company. pág. 238. ISBN 978-0716710448.
9. Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Uso de algoritmos de aproximación dual para problemas de planificación: resultados teóricos y prácticos". Revista de la ACM . 34 (1): 144–162. doi : 10.1145/7531.7535 . ISSN  0004-5411. S2CID  9739129.
10. Sahni, Sartaj K. (1 de enero de 1976). "Algoritmos para la programación de tareas independientes". Revista de la ACM . 23 (1): 116–127. doi : 10.1145/321921.321934 . ISSN  0004-5411. S2CID  10956951.
11. Woeginger, Gerhard J. (1997-05-01). "Un esquema de aproximación de tiempo polinomial para maximizar el tiempo mínimo de finalización de la máquina". Operations Research Letters . 20 (4): 149–154. doi :10.1016/S0167-6377(96)00055-7. ISSN  0167-6377.
12. Csirik, János; Kellerer, Hans; Woeginger, Gerhard (1 de junio de 1992). "El límite LPT exacto para maximizar el tiempo mínimo de finalización". Operations Research Letters . 11 (5): 281–287. doi :10.1016/0167-6377(92)90004-M. ISSN  0167-6377.
13. Jin, Kai (2017). "Particionamiento óptimo que maximiza la suma ponderada de productos". En Xiao, Mingyu; Rosamond, Frances (eds.). Frontiers in Algorithmics . Apuntes de clase en informática. Vol. 10336. Cham: Springer International Publishing. págs. 127–138. doi :10.1007/978-3-319-59605-1_12. ISBN 978-3-319-59605-1.
14. Alon, Noga; Azar, Yossi; Woeginger, Gerhard J.; Yadid, Tal (1998). "Esquemas de aproximación para la planificación en máquinas paralelas". Journal of Scheduling . 1 (1): 55–66. doi :10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN  1099-1425.
15. Korf, Richard E. (2009). Particionado de números multidireccional (PDF) . IJCAI .
16. Korf, Richard E. (20 de agosto de 1995). "De soluciones aproximadas a óptimas: un estudio de caso de partición de números". Actas de la 14.ª Conferencia conjunta internacional sobre inteligencia artificial, volumen 1. IJCAI'95. Montreal, Quebec, Canadá: Morgan Kaufmann Publishers Inc.: 266–272. ISBN 978-1-55860-363-9.
17. Korf, Richard E. (1998-12-01). "Un algoritmo completo en cualquier momento para la partición de números". Inteligencia artificial . 106 (2): 181–203. doi : 10.1016/S0004-3702(98)00086-1 . ISSN  0004-3702.
18. Schreiber, Ethan L.; Korf, Richard E.; Moffitt, Michael D. (25 de julio de 2018). "Particionamiento óptimo de números multidireccionales". Revista de la ACM . 65 (4): 24:1–24:61. doi : 10.1145/3184400 . ISSN  0004-5411. S2CID  63854223.
19. Korf, Richard E. (16 de julio de 2011). "Un algoritmo híbrido recursivo de partición de números multidireccional". Actas de la vigésimo segunda conferencia conjunta internacional sobre inteligencia artificial - Volumen uno . IJCAI'11. Barcelona, ​​Cataluña, España: AAAI Press: 591–596. ISBN 978-1-57735-513-7.
20. Schreiber, Ethan L.; Korf, Richard E. (3 de agosto de 2013). "Completado de bin mejorado para empaquetamiento de bin óptimo y partición de números" (PDF) . Actas de la vigésimo tercera conferencia conjunta internacional sobre inteligencia artificial . IJCAI '13. Pekín, China: AAAI Press: 651–658. ISBN 978-1-57735-633-2.
21. Moffitt, Michael D. (3 de agosto de 2013). "Estrategias de búsqueda para la partición óptima de números multidireccionales" (PDF) . Actas de la vigésimo tercera conferencia conjunta internacional sobre inteligencia artificial . IJCAI '13. Pekín, China: AAAI Press: 623–629. ISBN 978-1-57735-633-2.
22. Korf, Richard; Schreiber, Ethan (2 de junio de 2013). "Programación óptima de un pequeño número de máquinas paralelas idénticas". Actas de la Conferencia internacional sobre planificación y programación automatizadas . 23 : 144–152. doi : 10.1609/icaps.v23i1.13544 . ISSN  2334-0843. S2CID  12458816.
23. Schreiber, Ethan L.; Korf, Richard E. (27 de julio de 2014). "Debilitamiento iterativo en caché para particionamiento óptimo de números multidireccionales". Actas de la Conferencia AAAI sobre Inteligencia Artificial . AAAI'14. 28 . Ciudad de Quebec, Quebec, Canadá: AAAI Press: 2738–2744. doi : 10.1609/aaai.v28i1.9122 . S2CID  8594071.
24. Richard E. Korf, Ethan L. Schreiber y Michael D. Moffitt (2014). "Particionamiento secuencial óptimo de números multidireccionales" (PDF) .{{cite web}}: CS1 maint: multiple names: authors list (link)
25. Schreiber, Ethan L.; Korf, Richard E. (3 de agosto de 2013). "Completado de bin mejorado para empaquetamiento de bin óptimo y partición de números". Actas de la vigésimo tercera conferencia conjunta internacional sobre inteligencia artificial . IJCAI '13. Pekín, China: AAAI Press: 651–658. ISBN 978-1-57735-633-2.
26. Pop, Petrică C.; Matei, Oliviu (1 de noviembre de 2013). "Un enfoque de algoritmo memético para resolver el problema de partición de números multidimensionales y multidireccionales". Modelado matemático aplicado . 37 (22): 9191–9202. doi : 10.1016/j.apm.2013.03.075 . ISSN  0307-904X.