Elegir subconjuntos de un conjunto de tal manera que los subconjuntos satisfagan una restricción global

Question

Tenemos un conjunto de elementos $I = \{i_1, i_2, ..., i_n\}$ . Cada uno de estos elementos tiene lo que llamamos un p que es un número real. Queremos elegir un subconjunto de $I$ Llámalo $I'$ de tamaño $m$ (para algunos $m$ con $1 \le m \le n$ ) tal que la media de los p valores de los elementos en $I'$ se encuentra dentro de un rango especificado, $[p_l, p_u]$ . (Por ejemplo, podríamos exigir una media p entre 0,70 y 0,74). Además, queremos hacerlo de forma eficiente.

Esperamos hacerlo en tiempo O(n), pero cualquier algoritmo de tiempo polinómico es suficientemente bueno. Desde luego, no queremos limitarnos a probar todos los subconjuntos posibles de I de tamaño $m$ y luego comprobar si satisface la restricción del valor p medio.

Por último, haremos esto repetidamente y queremos que los subconjuntos elegidos sean una distribución aleatoria uniforme entre todos los subconjuntos posibles.

¿Hay alguna forma de hacerlo?

Answer 1

Suponiendo que $m$ es una entrada, su problema es NP-Completo.

La suma de subconjuntos puede reducirse a ella.

Dado $A = \{x_{1}, ..., x_{n}\}$ para la que necesitamos encontrar un subconjunto de suma $S$ podemos crear $n$ entradas a su algoritmo, con entrada $A$ , $m$ y $p_{L} = p_{U} = \frac{S}{m}$ para $1 \leq m \leq n$ .

Si $m$ es fijo, entonces el algoritmo de fuerza bruta (que no quieres) es $O(n^m)$ y por tanto tiene un algoritmo de tiempo polinómico.

Answer 2

Una solución que estaba considerando era elegir sucesivamente elementos para I' de tal manera que la media p de los elementos seleccionados hasta el momento siempre se encuentra dentro de unos límites superior e inferior.

Obviamente, podríamos simplemente elegir p_l y p_u como nuestros límites inferior y superior, respectivamente, y esto satisfaría la media p restricción de valor. Pero esto también sería demasiado restrictivo. Podría dejar fuera un gran número de posibles I' en los que pequeños p pueden equilibrar los valores p valores.

Así que estaba considerando dejar que los límites superior e inferior comiencen muy separados cuando se seleccionan los primeros elementos y luego dejar que se reduzcan a p_l y p_u cuando se selecciona el último elemento mth. Así tendríamos un cono de rangos que se estrecharía a medida que se seleccionan más elementos.

Más concretamente, definiríamos dos funciones u y l tal que la media de los primeros i elementos elegidos (llamémosle p_i) satisfaga l (i) <= p_i <= u (i) for 0 <= i <= m.

Sin embargo, no sé muy bien cómo definir estas dos funciones. Sé que l (m) = p_l y u (m) = p_u, pero no sé qué l (0) o u (0) debería ser. Además, ¿las funciones deben ser lineales?

Agradeceremos cualquier comentario o sugerencia sobre esta posible solución.