Suma de subconjuntos múltiples

El problema de la suma de subconjuntos múltiples es un problema de optimización en ciencias de la computación e investigación operativa . Es una generalización del problema de la suma de subconjuntos . La entrada al problema es un multiconjunto.${\displaystyle S}$de n enteros y un entero positivo m que representa el número de subconjuntos. El objetivo es construir, a partir de los enteros de entrada, algunos m subconjuntos. El problema tiene varias variantes:

• MSSP de suma máxima : para cada subconjunto j en 1,..., m , existe una capacidad C _j . El objetivo es hacer que la suma de todos los subconjuntos sea lo más grande posible, de modo que la suma en cada subconjunto j sea como máximo C _j . ^{[ 1 ]}
• MSSP de máximo-mínimo (también llamado MSSP de cuello de botella o BMSSP ): nuevamente, cada subconjunto tiene una capacidad, pero ahora el objetivo es hacer que la suma del subconjunto más pequeño sea lo más grande posible. ^{[ 1 ]}
• SSP justo : los subconjuntos no tienen capacidades fijas, sino que cada subconjunto pertenece a una persona diferente. La utilidad de cada persona es la suma de los elementos en sus subconjuntos. El objetivo es construir subconjuntos que satisfagan un criterio de equidad dado, como la asignación de elementos máximo-mínimo .

Cuando m es variable (parte de la entrada), ambos problemas son fuertemente NP-difíciles , por reducción a partir de la partición en 3. Esto significa que no tienen un esquema de aproximación totalmente polinomial (FPTAS) a menos que P=NP.

Incluso cuando m = 2, los problemas no tienen un FPTAS a menos que P = NP. Esto se puede demostrar mediante una reducción del problema de partición de cardinalidad igual (EPART):

• Dado un conjunto de instancias a ₁ ,..., a _n de EPART con suma objetivo T , construir un conjunto de instancias 2 T + a ₁ , ..., 2 T + a _n de MSSP con suma objetivo ( n +1) T para ambos subconjuntos.
• Una solución para EPART consta de dos partes, cada una con n /2 elementos cuya suma es T. Corresponde a una solución óptima de ambas variantes de MSSP: dos subconjuntos cuya suma es ( n +1) T , que es la mayor posible. De manera similar, cada solución óptima de MSSP corresponde a una solución para EPART.
• Cualquier solución no óptima para MSSP deja al menos un elemento sin asignar, por lo que su suma es como máximo 2 nT y su mínimo es como máximo nT . En ambas variantes, la razón de aproximación es como máximo${\displaystyle 1-1/(n+1)}$.
• Por lo tanto, para cualquier${\displaystyle \épsilon <1/(n+1)}$cualquier algoritmo con razón de aproximación${\displaystyle (1-\epsilon )}$Hay que encontrar la solución óptima, si es que existe.
• Si tuviéramos un FPTAS, entonces tendríamos un algoritmo con, por ejemplo,${\displaystyle \epsilon =1/(n+2)}$, con tiempo de ejecución polinomial en n . Este algoritmo podría usarse para resolver EPART en tiempo polinomial en n . Pero esto no es posible a menos que P=NP.

Se conocen los siguientes algoritmos de aproximación: ^{[ 1 ]}

• Para MSSP de suma máxima, con m variable :
  • Un PTAS, que se ejecuta en tiempo O( m+n ) cuando${\displaystyle \epsilon }$es fijo. El tiempo de ejecución es al menos exponencial en${\displaystyle 1/\epsilon ^{2}}$y los autores lo consideran poco práctico.
  • Un PTAS más general para el caso en que las capacidades de los subconjuntos son diferentes. ^{[ 2 ]}
  • Un algoritmo de aproximación 3/4 que se ejecuta en tiempo O( m ² n ). ^{[ 3 ]}
• Para MSSP máximo-mínimo:
  • Con m variable : una aproximación de 2/3, en tiempo O( n log n ). No es posible una mejor aproximación a menos que P=NP (por reducción de la partición de 3 ).
  • Con m fijo : un PTAS, funcionando en tiempo${\displaystyle O(n^{2m/\epsilon })}$.
  • Con un número fijo de valores de entrada distintos: un PTAS que utiliza el algoritmo de Lenstra .

El problema de la suma justa de subconjuntos ^{[ 4 ]} ( FSSP ) es una generalización del SSP en la que, después de seleccionar el subconjunto, sus elementos se asignan entre dos o más agentes. La utilidad de cada agente es igual a la suma de los pesos de los elementos que se le asignan. El objetivo es que el perfil de utilidad satisfaga algún criterio de equidad, como la regla igualitaria o la regla proporcional justa . Existen dos variantes del problema:

• Elementos compartidos : cada elemento puede asignarse a cada agente. Esta configuración es similar a la asignación justa de elementos con valoraciones idénticas (el valor de cada elemento es el mismo para todos los agentes y es igual al peso del elemento); sin embargo, existe una restricción de capacidad adicional en el peso total de los elementos. Como ejemplo, supongamos que los pesos de los elementos son 3, 5, 7, 9 y la capacidad es 15. Entonces, algunas asignaciones posibles son: ( {3,5,7}, {} ); ( {3,5}, {7} ); ( {5}, {3,7} ); ( {5}, {9} ). De estas asignaciones, la que satisface el criterio max-min es ( {3,5}, {7} ).
• Elementos separados : para cada agente, existe un conjunto separado de elementos que solo se le pueden asignar a él/ella. Esta configuración es relevante cuando hay un presupuesto que debe asignarse a diferentes proyectos, donde cada proyecto pertenece a un agente único.

Ambas variantes son NP-difíciles. Sin embargo, existen algoritmos de tiempo pseudopolinomial para enumerar todas las soluciones óptimas de Pareto cuando hay dos agentes: ^{[ 5 ]}

• Para elementos compartidos: defina una matriz bidimensional.${\displaystyle Q}$de tal manera que${\displaystyle Q(w_{1},w_{2})={\text{verdadero}}}$Si existe una solución que le dé un peso total de w _i al agente i , es posible enumerar todos los perfiles de utilidad posibles en el tiempo.${\displaystyle O(n\cdot c^{2})}$donde n es el número de artículos y c es el tamaño máximo de un artículo.
• Para elementos separados: para cada agente j , defina una matriz dinámica.${\displaystyle Q_{j}}$, de tal manera que${\displaystyle Q_{j}(w)={\text{verdadero}}}$Si existe una solución que le dé un peso total de w al agente j . Cada matriz${\displaystyle Q_{j}}$se pueden construir por separado utilizando los elementos separados del agente j . Luego, se pueden recorrer los dos arreglos en direcciones opuestas y enumerar todas las asignaciones en la frontera de Pareto. El tiempo de ejecución es${\displaystyle O(n\cdot c)}$.

Nicosia, Pacifici y Pferschy estudian el precio de la equidad , es decir, la relación entre la suma máxima de utilidades y la suma máxima de utilidades en una solución justa:

• Para artículos compartidos: el precio de equidad de la equidad max-min no tiene límites. Por ejemplo, supongamos que hay cuatro artículos con valores 1, e₁ , e₂ , e₃ , para algún e₁ > 0 pequeño. La suma máxima es 1, que se obtiene al darle a un agente el artículo con valor 1 y al otro agente nada. Pero la asignación max-min da a cada agente un valor de al menos e₁ , por lo que la suma debe ser como máximo 3e₁ . Por lo tanto, el precio de equidad es 1/(3e₁ ) , que no tiene límites.
• Alice tiene dos objetos con valores 1 y e , para algún valor pequeño de e > 0. George tiene dos objetos con valor e . La capacidad es 1. La suma máxima es 1, que se obtiene al darle a Alice el objeto con valor 1 y a George nada. Pero la asignación max-min da a ambos agentes el valor e . Por lo tanto, la POF es 1/(2 e ), que no está acotada.
• Para elementos separados: el precio de equidad de la equidad max-min no tiene límites. Por ejemplo, supongamos que Alice tiene dos elementos con valores 1 y e , para algún e > 0 pequeño. George tiene dos elementos con valor e . La capacidad es 1. La suma máxima es 1, cuando Alice obtiene el elemento con valor 1 y George no obtiene nada. Pero la asignación max-min da a ambos agentes el valor e . Por lo tanto, el POF es 1/(2 e ), que no tiene límites.

En ambos casos, si el valor del elemento está acotado por alguna constante a , entonces el POF está acotado por una función de a . ^{[ 5 ]}

El problema de la mochila múltiple (MKP) es una generalización tanto del problema de la suma máxima de objetos (MSSP) como del problema de la mochila . En este problema, hay m mochilas y n objetos, donde cada objeto tiene un valor y un peso. El objetivo es llenar las m mochilas con el mayor valor posible, de manera que el peso total en cada una sea como máximo su capacidad.

• El MSSP de suma máxima es un caso especial de MKP en el que el valor de cada elemento es igual a su peso.
• El problema de la mochila es un caso especial del problema de la mochila múltiple en el que m = 1.
• El problema de la suma de subconjuntos es un caso especial de MKP en el que el valor de cada elemento es igual a su peso, y m = 1.

El MKP tiene un esquema de aproximación de tiempo polinomial . ^{[ 6 ]}