Maximización submodular no monótona con restricciones de cardinalidad

Question

¿Existe algún algoritmo de aproximación para la maximización funciones submodulares no monótonas que puede tener valores negativos o sin límites por debajo?

Dato 1: Para funciones submodulares monótonas Nemhauser, Wolsey y Fisher demostraron [1] ese simple algoritmo codicioso da $1-1/e$ garantía de aproximación.

Hecho 2: Para funciones submodulares no monótonas no negativas Buchbinder y otros han demostrado que [2] que el algoritmo aleatorio codicioso da $1/e$ aproximación para la restricción de cardinalidad.

Answer 1

Ha habido una línea de trabajo reciente que investiga algoritmos para problemas de optimización submodular cuando el objetivo puede tomar valores negativos. Hasta ahora, la no negatividad que podemos manejar es cuando el objetivo submodular se descompone en la suma de una función submodular monótona y una función modular arbitraria. El problema de optimización es $$ \max_{S \in \mathcal{I}} g(S) - c(S) \enspace,$$ donde $g:2^V \rightarrow \mathbb{R}_+$ es una función submodular no negativa y monótona, $c:2^V \rightarrow \mathbb{R}$ es una función modular, y $\mathcal{I} \subset 2^V$ es un matroide en el conjunto de tierra $V$ . Tenga en cuenta que si $c$ toma valores positivos, entonces el objetivo submodular completo $f = g - c$ no es monótona y puede tomar valores negativos. El resultado de la primera aproximación viene dado por Sviridenko, Vondrák y Ward en 2014 que demostró que se puede utilizar un enfoque de extensión y redondeo continuo para obtener un conjunto $S$ tal que $$ g(S) - c(S) \geq (1 - e^{-1}) g(OPT) - c(OPT) $$ Aplicaron este resultado para obtener garantías de aproximación ajustada para la maximización submodular monótona y la minimización supermodular monótona con curvatura acotada. También muestran que esta aproximación es ajustada en el sentido de que ningún algoritmo que realice un número polinomial de consultas a $g$ y $c$ puede hacerlo mejor. Entonces en 2018, Feldman dio un algoritmo que también recorre el dominio continuo, pero que es más eficiente en el sentido de que obvia cierto "paso de adivinación" del algoritmo anterior. Más recientemente, Harshaw, Feldman, Karbasi y Ward en 2019 dieron una serie de algoritmos mucho más rápidos que no pasan por la extensión continua, sino que se basan en la optimización codiciosa de un "objetivo sustituto distorsionado" que cambia a lo largo del algoritmo; sin embargo, sus resultados sólo se aplican cuando la función modular es no negativa y la restricción es una restricción de cardinalidad. También amplían el análisis para demostrar que cuando $g$ es $\gamma$ -débilmente submodular, entonces se puede obtener la aproximación análoga $$ g(S) - c(S) \geq (1 - e^{-\gamma}) g(OPT) - c(OPT) $$ Además, esta garantía de aproximación ampliada es estricta en el modelo de oráculo de valor.

Como ha señalado notwatson, existe el resultado de dureza de Uriel Feige que muestra que incluso verificando que $f(S) \geq 0$ para algunos $S$ es NP-Difícil. Así que la descomposición en una suma de funciones submodulares y monótonas es realmente crucial en todos estos algoritmos. No sé hasta dónde se puede llevar el enfoque de la descomposición.

Answer 2

Existe un trabajo "Maximizing Non-Monotone Submodular Functions" de Uriel Feige, en el que se demuestra que incluso verificando la existencia de alguna $S \subseteq \Omega$ tal que $f(S) > 0 $ es NP-difícil para funciones submodulares (no limitadas). Esto implica que el caso acotado también es NP-difícil.

En el caso de que $f$ está limitada por debajo por $-M,$ se puede considerar la función submodular $\tilde{f}(X) = f(X) + M,$ que no es negativo. Utilizando métodos estándar para funciones submodulares no negativas en $\tilde{f},$ se puede obtener una aproximación al máximo de $f.$ Sin embargo, ya no será una aproximación de factor constante. En particular, la constante $M$ aparecerá en el límite de aproximación.

En el caso de que $f$ es ilimitado por debajo, no conozco ninguna solución para las funciones submodulares generales. Sin embargo, si su conjunto de tierra $\Omega$ es finito, parece que $f$ tendría que ser muy patológico para no tener límites por debajo (o por encima). Si ese es el caso, probablemente habría que considerar la estructura de las funciones en particular para poder avanzar.