Suma de subconjuntos múltiples

El problema de la suma de subconjuntos múltiples es un problema de optimización en informática e investigación de operaciones . Es una generalización del problema de la suma de subconjuntos . La entrada del problema es un multiconjunto 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: ${\estilo de visualización S}$

Suma máxima MSSP : 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]
Max-min MSSP (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, pero cada subconjunto pertenece a una persona diferente. La utilidad de cada persona es la suma de los elementos de sus subconjuntos. El objetivo es construir subconjuntos que satisfagan un criterio de equidad dado, como la asignación máxima-mínima de elementos .

Suma máxima y mínimo máximo MSSP

Cuando m es variable (una parte de la entrada), ambos problemas son fuertemente NP-hard , por reducción de 3-partición . Esto significa que no tienen un esquema de aproximación de tiempo polinomial completo (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 igual cardinalidad (EPART):

Dada una instancia a ₁ ,..., a _n de EPART con suma objetivo T , construya una instancia 2 T + a ₁ , ..., 2 T + a _n de MSSP con suma objetivo ( n +1) T para ambos subconjuntos.
Una solución de EPART consta de dos partes, cada una de las cuales tiene n /2 elementos con una suma de T . Corresponde a una solución óptima de ambas variantes de MSSP: dos subconjuntos con una suma de ( n +1) T , que es la mayor posible. De manera similar, cada solución óptima de MSSP corresponde a una solución de 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 . ${\estilo de visualización 1-1/(n+1)}$
Por lo tanto, para cualquier , cualquier algoritmo con razón de aproximación debe encontrar la solución óptima si existe. $\épsilon <1/(n+1)$ $(1-\epsilon )$
Si tuviéramos un FPTAS, tendríamos un algoritmo con, por ejemplo , un polinomio de tiempo de ejecución en n . Este algoritmo podría usarse para resolver EPART en un polinomio de tiempo en n . Pero esto no es posible a menos que P=NP. $\epsilon =1/(n+2)$

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

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

Problema de suma de subconjuntos justos

El problema de la suma de subconjuntos justos ^[4] ( FSSP ) es una generalización del SSP en el 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 . Dos variantes del problema son:

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 máximo-mínimo 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 se debe asignar a diferentes proyectos, donde cada proyecto pertenece a un agente único.

Ambas variantes son NP-hard. 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 tal que si y solo si existe una solución que otorga un peso total de w _i al agente i . Es posible enumerar todos los perfiles de utilidad posibles en el tiempo donde n es la cantidad de elementos y c es el tamaño máximo de un elemento. ${\estilo de visualización Q}$ $Q(w_{1},w_{2})={\text{verdadero}}$ $O(n\cdot c^{2})$
Para elementos separados: para cada agente j , defina una matriz dinámica , tal que si y solo si existe una solución que le dé un peso total de w al agente j . Cada matriz se puede construir por separado utilizando los elementos separados del agente j . Luego, se pueden recorrer las dos matrices en direcciones opuestas y enumerar todas las asignaciones en la frontera de Pareto. El tiempo de ejecución es . $Q_{j}$ $Q_{j}(w)={\text{verdadero}}$ $Q_{j}$ $O(n\cdot c)$

Nicosia, Pacifici y Pferschy estudian el precio de la justicia , 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 los elementos compartidos: el precio de justicia de la equidad máxima-mínima no tiene límites. Por ejemplo, supongamos que hay cuatro elementos con valores 1, e , e , e , para un valor pequeño de e > 0. La suma máxima es 1, que se obtiene al dar a un agente el elemento con valor 1 y al otro agente nada. Pero la asignación máxima-mínima da a cada agente un valor de al menos e , por lo que la suma debe ser como máximo 3 e . Por lo tanto, el POF es 1/(3 e ), que no tiene límites.
Alice tiene dos elementos con valores 1 y e , para un valor pequeño de e > 0. George tiene dos elementos con valor e . La capacidad es 1. La suma máxima es 1, que se obtiene al darle a Alice el elemento con valor 1 y a George nada. Pero la asignación máxima-mínima les da a ambos agentes el valor e . Por lo tanto, la POF es 1/(2 e ), que no tiene límites.
Para artículos separados: el precio de justicia de la equidad máxima-mínima no tiene límites. Por ejemplo, supongamos que Alice tiene dos artículos con valores 1 y e , para un valor pequeño de e > 0. George tiene dos artículos con valor e . La capacidad es 1. La suma máxima es 1 - cuando Alice obtiene el artículo con valor 1 y George no obtiene nada. Pero la asignación máxima-mínima les 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á limitado por alguna constante a , entonces el POF está limitado por una función de a . ^[5]

Problema de múltiples mochilas

El problema de las mochilas múltiples (MKP) es una generalización tanto del MSSP de suma máxima como del problema de las mochilas . En este problema, hay m mochilas y n artículos, donde cada artículo tiene un valor y un peso. El objetivo es colocar la mayor cantidad de valor posible en los m contenedores, de modo que el peso total en cada contenedor sea como máximo su capacidad.

Max-sum MSSP es un caso especial de MKP en el que el valor de cada artículo es igual a su peso.
El problema de la mochila es un caso especial de MKP 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]

Referencias

^ abc Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (1 de febrero de 2000). "El problema de la suma de subconjuntos múltiples". Revista SIAM sobre optimización . 11 (2): 308–319. doi :10.1137/S1052623498348481. ISSN 1052-6234.
^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (29 de febrero de 2000). "Un PTAS para el problema de suma de subconjuntos múltiples con diferentes capacidades de mochila". Information Processing Letters . 73 (3–4): 111–118. doi :10.1016/S0020-0190(00)00010-7. ISSN 0020-0190.
^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (1 de marzo de 2003). "Un algoritmo de aproximación 3/4 para la suma de múltiples subconjuntos". Journal of Heuristics . 9 (2): 99–111. doi :10.1023/A:1022584312032. ISSN 1572-9397. S2CID 1120180.
^ Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2015). Hoefer, Martin (ed.). "Breve anuncio: sobre el problema de la suma de subconjuntos justos". Teoría de juegos algorítmica . Apuntes de clase en informática. 9347 . Berlín, Heidelberg: Springer: 309–311. doi :10.1007/978-3-662-48433-3_28. ISBN 978-3-662-48433-3.
^ ab Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (16 de marzo de 2017). "Precio de justicia para asignar un recurso limitado". Revista Europea de Investigación Operativa . 257 (3): 933–943. arXiv : 1508.05253 . doi :10.1016/j.ejor.2016.08.013. ISSN 0377-2217. S2CID 14229329.
^ Chandra Chekuri y Sanjeev Khanna (2005). "Un PTAS para el problema de múltiples mochilas". Revista SIAM de Computación . 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . doi :10.1137/s0097539700382820.