Redondeo aleatorio

Arreglar${\displaystyle \lambda =\ln(2|{\mathcal {U}}|)}$Con probabilidad positiva, el esquema de redondeo devuelve una cobertura de conjunto.${\displaystyle x'}$de costo como máximo${\displaystyle 2\ln(2|{\mathcal {U}}|)c\cdot x^{*}}$(y por lo tanto de costo)${\displaystyle O(\log |{\mathcal {U}}|)}$veces el coste de la cobertura óptima del conjunto).

(Nota: con cuidado el ${\displaystyle O(\log |{\mathcal {U}}|)}$puede reducirse a${\displaystyle \ln(|{\mathcal {U}}|)+O(\log \log |{\mathcal {U}}|)}$.)

La salida${\displaystyle x'}$El esquema de redondeo aleatorio tiene las propiedades deseadas siempre que no ocurra ninguno de los siguientes eventos "malos":

1. el costo${\displaystyle c\cdot x'}$de${\displaystyle x'}$supera${\displaystyle 2\lambda c\cdot x^{*}}$, o
2. para algún elemento${\displaystyle e}$,${\displaystyle x'}$no logra cubrir${\displaystyle e}$.

La expectativa de cada ${\displaystyle x'_{s}}$es como máximo${\displaystyle \lambda x_{s}^{*}}$. Por linealidad de la esperanza , la esperanza de ${\displaystyle c\cdot x'}$ es como máximo${\displaystyle \sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot x^{*}}$Por lo tanto, según la desigualdad de Markov , la probabilidad del primer evento malo mencionado anteriormente es como máximo${\displaystyle 1/2}$.

Para los eventos malos restantes (uno por cada elemento)${\displaystyle e}$), tenga en cuenta que, dado que${\displaystyle \sum _{s\ni e}x_{s}^{*}\geq 1}$para cualquier elemento dado${\displaystyle e}$, la probabilidad de que${\displaystyle e}$no está cubierto es

${\displaystyle {\begin{aligned}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s}^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2|{\mathcal {U}}|).\end{aligned}}}$

(Esto utiliza la desigualdad${\displaystyle 1+z\leq e^{z}}$, que es estricto para${\displaystyle z\neq 0}$.)

Así, para cada uno de los${\displaystyle |{\mathcal {U}}|}$elementos, la probabilidad de que el elemento no esté cubierto es menor que${\displaystyle 1/(2{\mathcal {U}})}$.

Por el límite de unión , la probabilidad de que uno de los${\displaystyle 1+|{\mathcal {U}}|}$Los eventos malos ocurren con menos frecuencia que${\displaystyle 1/2+|{\mathcal {U}}|/(2{\mathcal {U}})=1}$. Por lo tanto, con probabilidad positiva no hay eventos malos y${\displaystyle x'}$es una cobertura fija de costo como máximo${\displaystyle 2\lambda c\cdot x^{*}}$QED

Queremos poder configurar cada variable.${\displaystyle x'_{s}}$a su vez, para mantener la probabilidad condicional de fallo por debajo de 1. Para ello, necesitamos una buena cota para la probabilidad condicional de fallo. La cota se obtendrá refinando la prueba de existencia original. Dicha prueba acota implícitamente la probabilidad de fallo mediante la esperanza de la variable aleatoria.

${\displaystyle F={\frac {c\cdot x'}{2\lambda c\cdot x^{*}}}+|{\mathcal {U}}^{(m)}|}$,

dónde

${\displaystyle {\mathcal {U}}^{(m)}={\Big \{}e:\prod _{s\ni e}(1-x'_{s})=1{\Big \}}}$

es el conjunto de elementos que quedan sin descubrir al final.

La variable aleatoria${\displaystyle F}$Puede parecer un poco misterioso, pero refleja la prueba probabilística de forma sistemática. El primer término en${\displaystyle F}$Proviene de aplicar la desigualdad de Markov para acotar la probabilidad del primer evento malo (el costo es demasiado alto). Contribuye al menos 1 a${\displaystyle F}$si el costo de${\displaystyle x'}$es demasiado alto. El segundo término cuenta el número de eventos malos del segundo tipo (elementos no cubiertos). Contribuye al menos con 1 a${\displaystyle F}$si${\displaystyle x'}$deja cualquier elemento sin cubrir. Por lo tanto, en cualquier resultado donde${\displaystyle F}$es menor que 1, ${\displaystyle x'}$debe cubrir todos los elementos y tener un costo que cumpla con el límite deseado del lema. En resumen, si el paso de redondeo falla, entonces${\displaystyle F\geq 1}$Esto implica (por la desigualdad de Markov ) que ${\displaystyle E[F]}$es una cota superior de la probabilidad de fallo. Nótese que el argumento anterior ya está implícito en la demostración del lema, que también muestra mediante cálculo que${\displaystyle E[F]<1}$.

Para aplicar el método de probabilidades condicionales, necesitamos extender el argumento para acotar la probabilidad condicional de fallo a medida que avanza el redondeo. Por lo general, esto se puede hacer de forma sistemática, aunque puede resultar técnicamente laborioso.

Entonces, ¿qué ocurre con la probabilidad condicional de fallo a medida que el paso de redondeo itera a través de los conjuntos? Dado que${\displaystyle F\geq 1}$en cualquier resultado donde el paso de redondeo falla, por la desigualdad de Markov , la probabilidad condicional de falla es como máximo la esperanza condicional de${\displaystyle F}$.

A continuación calculamos la esperanza condicional de${\displaystyle F}$, de forma similar a como calculamos la esperanza no condicionada de${\displaystyle F}$en la demostración original. Considere el estado del proceso de redondeo al final de alguna iteración.${\displaystyle t}$. Dejar${\displaystyle S^{(t)}}$denotamos los conjuntos considerados hasta ahora (el primero${\displaystyle t}$conjuntos en${\displaystyle {\mathcal {S}}}$). Dejar${\displaystyle x^{(t)}}$denotemos el vector (parcialmente asignado)${\displaystyle x'}$ (entonces${\displaystyle x_{s}^{(t)}}$se determina solo si${\displaystyle s\in S^{(t)}}$). Para cada conjunto${\displaystyle s\not \in S^{(t)}}$, dejar${\displaystyle p_{s}=\min(\lambda x_{s}^{*},1)}$ denotemos la probabilidad con la que${\displaystyle x'_{s}}$se establecerá en 1. Deje${\displaystyle {\mathcal {U}}^{(t)}}$contienen los elementos aún no cubiertos. Entonces la expectativa condicional de${\displaystyle F}$, dadas las decisiones tomadas hasta ahora, es decir, dadas${\displaystyle x^{(t)}}$, es

${\displaystyle E[F|x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

Tenga en cuenta que${\displaystyle E[F|x^{(t)}]}$se determina solo después de la iteración${\displaystyle t}$.

Para mantener la probabilidad condicional de falla por debajo de 1, basta con mantener la esperanza condicional de${\displaystyle F}$por debajo de 1. Para ello, basta con mantener la expectativa condicional de${\displaystyle F}$desde el aumento. Esto es lo que hará el algoritmo. Establecerá${\displaystyle x'_{s}}$en cada iteración para asegurar que

${\displaystyle E[F|x^{(m)}]\leq E[F|x^{(m-1)}]\leq \cdots \leq E[F|x^{(1)}]\leq E[F|x^{(0)}]<1}$

(dónde${\displaystyle m=|{\mathcal {S}}|}$).

En el${\displaystyle t}$En la iteración , ¿cómo puede el algoritmo establecer${\displaystyle x'_{s'}}$ para asegurar que${\displaystyle E[F|x^{(t)}]\leq E[F|S^{(t-1)}]}$¿Resulta que simplemente puede configurarlo?${\displaystyle x'_{s'}}$ para minimizar el valor resultante de${\displaystyle E[F|x^{(t)}]}$.

Para ver por qué, concéntrese en el momento en que la iteración${\displaystyle t}$comienza. En ese momento,${\displaystyle E[F|x^{(t-1)}]}$está determinado, pero${\displaystyle E[F|x^{(t)}]}$aún no está determinado --- puede tomar dos valores posibles dependiendo de cómo${\displaystyle x'_{s'}}$ está configurado en iteración${\displaystyle t}$. Dejar${\displaystyle E^{(t-1)}}$denota el valor de${\displaystyle E[F|x'^{(t-1)}]}$. Dejar${\displaystyle E_{0}^{(t)}}$y${\displaystyle E_{1}^{(t)}}$, denotan los dos posibles valores de ${\displaystyle E[F|x^{(t)}]}$, dependiendo de si${\displaystyle x'_{s'}}$se establece en 0 o 1, respectivamente. Por la definición de esperanza condicional,

${\displaystyle E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{(t)}+\Pr[x'_{s'}=1]E_{1}^{(t)}.}$

Dado que el promedio ponderado de dos cantidades es siempre al menos el mínimo de esas dos cantidades, se deduce que

${\displaystyle E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).}$

Por lo tanto, estableciendo${\displaystyle x'_{s'}}$ para minimizar el valor resultante de ${\displaystyle E[F|x^{(t)}]}$ garantizará que ${\displaystyle E[F|x^{(t)}]\leq E[F|x^{(t-1)}]}$Esto es lo que hará el algoritmo.

En detalle, ¿qué significa esto? Considerado como una función de${\displaystyle x'_{s'}}$ (con todas las demás cantidades fijas) ${\displaystyle E[F|x^{(t)}]}$ es una función lineal de${\displaystyle x'_{s'}}$y el coeficiente de${\displaystyle x'_{s'}}$en esa función es

${\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}~-~\sum _{e\in s'\cap {\mathcal {U}}_{t-1}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

Por lo tanto, el algoritmo debería establecer${\displaystyle x'_{s'}}$a 0 si esta expresión es positiva, y 1 en caso contrario. Esto da como resultado el siguiente algoritmo.

El algoritmo anterior devuelve una cobertura de conjunto.${\displaystyle x'}$de costo como máximo${\displaystyle 2\ln(2|{\mathcal {U}}|)}$veces el costo mínimo de cualquier cobertura de conjunto (fraccional).

El algoritmo garantiza que la expectativa condicional de${\displaystyle F}$, ${\displaystyle E[F\,|\,x^{(t)}]}$, no aumenta en cada iteración. Dado que esta expectativa condicional es inicialmente menor que 1 (como se mostró anteriormente), el algoritmo garantiza que la expectativa condicional se mantenga por debajo de 1. Dado que la probabilidad condicional de falla es como máximo la expectativa condicional de${\displaystyle F}$De esta forma, el algoritmo garantiza que la probabilidad condicional de fallo se mantenga por debajo de 1. Así, al final, cuando se determinan todas las opciones, el algoritmo alcanza un resultado satisfactorio. Es decir, el algoritmo anterior devuelve una cobertura de conjunto.${\displaystyle x'}$ de costo como máximo${\displaystyle 2\ln(2|{\mathcal {U}}|)}$veces el costo mínimo de cualquier cobertura de conjunto (fraccional).