Redondeo aleatorio

En informática e investigación de operaciones , el redondeo aleatorio ^[1] es un enfoque ampliamente utilizado para diseñar y analizar algoritmos de aproximación . ^{[2] [3]}

Muchos problemas de optimización combinatoria son computacionalmente intratables para resolverlos con exactitud (hasta el punto óptimo). Para tales problemas, se puede utilizar el redondeo aleatorio para diseñar algoritmos de aproximación rápidos ( tiempo polinomial ) , es decir, algoritmos que garantizan que devolverán una solución aproximadamente óptima dada cualquier entrada.

La idea básica del redondeo aleatorio es convertir una solución óptima de una relajación del problema en una solución aproximadamente óptima del problema original. El algoritmo resultante se suele analizar utilizando el método probabilístico .

Descripción general

El enfoque básico tiene tres pasos:

1. Formular el problema a resolver como un programa lineal entero (ILP).
2. Calcule una solución fraccionaria óptima para la relajación de programación lineal (LP) del ILP. ${\displaystyle x}$
3. Redondea la solución fraccionaria del PL a una solución entera del PL. ${\displaystyle x}$ ${\displaystyle x'}$

(Aunque el enfoque se aplica más comúnmente con programas lineales, a veces se utilizan otros tipos de relajaciones. Por ejemplo, consulte el algoritmo de aproximación Max-Cut basado en programación semidefinida de Goemans y Williamson ).

En el primer paso, el desafío consiste en elegir un programa lineal entero adecuado. Se requiere familiaridad con la programación lineal, en particular con el modelado mediante programas lineales y programas lineales enteros. Para muchos problemas, existe un programa lineal entero natural que funciona bien, como en el ejemplo de Set Cover que se muestra a continuación. (El programa lineal entero debe tener una pequeña brecha de integralidad ; de hecho, el redondeo aleatorio se utiliza a menudo para demostrar límites en las brechas de integralidad).

En el segundo paso, la solución fraccionaria óptima normalmente se puede calcular en tiempo polinomial utilizando cualquier algoritmo de programación lineal estándar .

En el tercer paso, la solución fraccionaria debe convertirse en una solución entera (y, por lo tanto, en una solución del problema original). Esto se llama redondear la solución fraccionaria. La solución entera resultante debería tener un costo (probablemente) no mucho mayor que el costo de la solución fraccionaria. Esto garantizará que el costo de la solución entera no sea mucho mayor que el costo de la solución entera óptima.

La técnica principal que se utiliza para realizar el tercer paso (redondeo) es utilizar la aleatorización y luego utilizar argumentos probabilísticos para limitar el aumento del costo debido al redondeo (siguiendo el método probabilístico de la combinatoria). En este caso, se utilizan argumentos probabilísticos para demostrar la existencia de estructuras discretas con las propiedades deseadas. En este contexto, se utilizan dichos argumentos para demostrar lo siguiente:

Dada cualquier solución fraccionaria del PL, con probabilidad positiva el proceso de redondeo aleatorio produce una solución entera que se aproxima ${\displaystyle x}$ ${\displaystyle x'}$ ${\displaystyle x}$ de acuerdo con algún criterio deseado.

Finalmente, para que el tercer paso sea computacionalmente eficiente, se demuestra que se aproxima con alta probabilidad (para que el paso pueda seguir siendo aleatorio) o se desaleatoriza el paso de redondeo, generalmente utilizando el método de probabilidades condicionales . El último método convierte el proceso de redondeo aleatorio en un proceso determinista eficiente que garantiza alcanzar un buen resultado. ${\displaystyle x'}$ ${\displaystyle x}$

Ejemplo: el problema de la cubierta del set

El siguiente ejemplo ilustra cómo se puede utilizar el redondeo aleatorio para diseñar un algoritmo de aproximación para el problema de cobertura de conjuntos . Corrija cualquier instancia de cobertura de conjuntos en un universo . ${\displaystyle \langle c,{\mathcal {S}}\rangle }$ ${\displaystyle {\mathcal {U}}}$

Calcular la solución fraccionaria

Para el paso 1 , sea IP el programa lineal entero estándar para la cobertura del conjunto para esta instancia.

Para el paso 2 , sea LP la relajación de programación lineal de IP y calcule una solución óptima para LP utilizando cualquier algoritmo de programación lineal estándar. Esto requiere un polinomio de tiempo en el tamaño de entrada. Las soluciones factibles para LP son los vectores que asignan a cada conjunto un peso no negativo , de modo que, para cada elemento , cubra —el peso total asignado a los conjuntos que contienen es al menos 1, es decir, ${\displaystyle x^{*}}$ ${\displaystyle x}$ ${\displaystyle s\in {\mathcal {S}}}$ ${\displaystyle x_{s}}$ ${\displaystyle e\in {\mathcal {U}}}$ ${\displaystyle x'}$ ${\displaystyle e}$ ${\displaystyle e}$

${\displaystyle \sum _{s\ni e}x_{s}\geq 1.}$

La solución óptima es una solución factible cuyo costo ${\displaystyle x^{*}}$

${\displaystyle \sum _{s\in {\mathcal {S}}}c(S)x_{s}^{*}}$

es lo más pequeño posible. Nótese que cualquier conjunto de cobertura para da una solución factible (donde para , en caso contrario). El costo de esto es igual al costo de , es decir, ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle x}$ ${\displaystyle x_{s}=1}$ ${\displaystyle s\in {\mathcal {C}}}$ ${\displaystyle x_{s}=0}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle x}$

${\displaystyle \sum _{s\in {\mathcal {C}}}c(s)=\sum _{s\in {\mathcal {S}}}c(s)x_{s}.}$

En otras palabras, el programa lineal LP es una relajación del problema de cobertura de conjuntos dado.

Dado que tiene un costo mínimo entre las soluciones factibles para el LP, el costo de es un límite inferior del costo del conjunto óptimo cubrir . ${\displaystyle x^{*}}$ ${\displaystyle x^{*}}$

Paso de redondeo aleatorio

En el paso 3 , debemos convertir la cobertura de conjunto fraccionaria de costo mínimo en una solución entera factible (que corresponde a una cobertura de conjunto verdadera). El paso de redondeo debe producir un que, con probabilidad positiva, tenga un costo dentro de un factor pequeño del costo de . Entonces (ya que el costo de es un límite inferior del costo de la cobertura de conjunto óptima), el costo de estará dentro de un factor pequeño del costo óptimo. ${\displaystyle x^{*}}$ ${\displaystyle x'}$ ${\displaystyle x'}$ ${\displaystyle x^{*}}$ ${\displaystyle x^{*}}$ ${\displaystyle x'}$

Como punto de partida, considere el esquema de redondeo más natural:

Para cada conjunto , tome a su vez con probabilidad , de lo contrario tome . ${\displaystyle s\in {\mathcal {S}}}$ ${\displaystyle x'_{s}=1}$ ${\displaystyle \min(1,x_{s}^{*})}$ ${\displaystyle x'_{s}=0}$

Con este esquema de redondeo, el costo esperado de los conjuntos elegidos es como máximo , el costo de la cobertura fraccionaria. Esto es bueno. Desafortunadamente, la cobertura no es buena. Cuando las variables son pequeñas, la probabilidad de que un elemento no esté cubierto es de aproximadamente ${\displaystyle \sum _{s}c(s)x_{s}^{*}}$ ${\displaystyle x_{s}^{*}}$ ${\displaystyle e}$

${\displaystyle \prod _{s\ni e}1-x_{s}^{*}\approx \prod _{s\ni e}\exp(-x_{s}^{*})=\exp {\Big (}-\sum _{s\ni e}x_{s}^{*}{\Big )}\approx \exp(-1).}$

Por lo tanto, solo una fracción constante de los elementos quedará cubierta según las expectativas.

Para cubrir cada elemento con alta probabilidad, el esquema de redondeo estándar primero aumenta las probabilidades de redondeo por un factor apropiado . Este es el esquema de redondeo estándar: ${\displaystyle x'}$ ${\displaystyle \lambda >1}$

Fijar un parámetro . Para cada conjunto, por turno, ${\displaystyle \lambda \geq 1}$ ${\displaystyle s\in {\mathcal {S}}}$

tomar con probabilidad , de lo contrario tomar . ${\displaystyle x'_{s}=1}$ ${\displaystyle \min(\lambda x_{s}^{*},1)}$ ${\displaystyle x'_{s}=0}$

Aumentar las probabilidades en , aumenta el costo esperado en , pero hace que la cobertura de todos los elementos sea probable. La idea es elegir el valor más pequeño posible para que todos los elementos estén cubiertos de manera demostrable con una probabilidad distinta de cero. A continuación, se incluye un análisis detallado. ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$

---

Lema (garantía de aproximación para el esquema de redondeo)

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

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

Prueba

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

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

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

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

${\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 , que es estricta para ). ${\displaystyle 1+z\leq e^{z}}$ ${\displaystyle z\neq 0}$

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

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

Desaleatorización mediante el método de probabilidades condicionales

El lema anterior muestra la existencia de un conjunto de cobertura de costos ). En este contexto, nuestro objetivo es un algoritmo de aproximación eficiente, no solo una prueba de existencia, por lo que no hemos terminado. ${\displaystyle O(\log(|{\mathcal {U}}|)c\cdot x^{*}}$

Un enfoque sería aumentar un poco y luego demostrar que la probabilidad de éxito es al menos, digamos, 1/4. Con esta modificación, repetir el paso de redondeo aleatorio unas cuantas veces es suficiente para garantizar un resultado exitoso con alta probabilidad. ${\displaystyle \lambda }$

Ese enfoque debilita la razón de aproximación. A continuación, describimos un enfoque diferente que produce un algoritmo determinista que garantiza que coincida con la razón de aproximación de la prueba de existencia anterior. El enfoque se denomina método de probabilidades condicionales .

El algoritmo determinista emula el esquema de redondeo aleatorio: considera cada conjunto por turno y elige . Pero en lugar de hacer cada elección aleatoriamente en función de , hace la elección de manera determinista , de modo de mantener la probabilidad condicional de falla, dadas las elecciones realizadas hasta el momento, por debajo de 1 . ${\displaystyle s\in {\mathcal {S}}}$ ${\displaystyle x'_{s}\in \{0,1\}}$ ${\displaystyle x^{*}}$

Limitación de la probabilidad condicional de fallo

Queremos poder establecer cada variable a su vez de modo que la probabilidad condicional de falla se mantenga por debajo de 1. Para ello, necesitamos un buen límite para la probabilidad condicional de falla. El límite se obtendrá refinando la prueba de existencia original. Esa prueba limita implícitamente la probabilidad de falla por la expectativa de la variable aleatoria. ${\displaystyle x'_{s}}$

${\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 descubiertos al final.

La variable aleatoria puede parecer un poco misteriosa, pero refleja la prueba probabilística de una manera sistemática. El primer término en proviene de aplicar la desigualdad de Markov para limitar la probabilidad del primer evento malo (el costo es demasiado alto). Contribuye al menos 1 a si el costo de es demasiado alto. El segundo término cuenta el número de eventos malos del segundo tipo (elementos descubiertos). Contribuye al menos 1 a si deja algún elemento descubierto. Por lo tanto, en cualquier resultado donde es menor que 1, 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 . Esto implica (por la desigualdad de Markov ) que es un límite superior en la probabilidad de falla. Nótese que el argumento anterior ya está implícito en la prueba del lema, que también muestra por cálculo que . ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle x'}$ ${\displaystyle F}$ ${\displaystyle x'}$ ${\displaystyle F}$ ${\displaystyle x'}$ ${\displaystyle F\geq 1}$ ${\displaystyle E[F]}$ ${\displaystyle E[F]<1}$

Para aplicar el método de probabilidades condicionales, necesitamos extender el argumento para limitar la probabilidad condicional de falla a medida que avanza el paso de redondeo. Por lo general, esto se puede hacer de manera sistemática, aunque puede resultar tedioso desde el punto de vista técnico.

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

A continuación calculamos la esperanza condicional de , de forma muy similar a como calculamos la esperanza incondicionada de en la prueba original. Consideremos el estado del proceso de redondeo al final de alguna iteración . Sea , denotemos los conjuntos considerados hasta ahora (los primeros conjuntos en ). Sea , denotemos el vector (parcialmente asignado) (por lo que se determina solo si ). Para cada conjunto , sea , denotemos la probabilidad con la que se establecerá en 1. Sea , contenga los elementos aún no cubiertos. Entonces, la esperanza condicional de , dadas las elecciones realizadas hasta ahora, es decir, dado , es ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle t}$ ${\displaystyle S^{(t)}}$ ${\displaystyle t}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle x^{(t)}}$ ${\displaystyle x'}$ ${\displaystyle x_{s}^{(t)}}$ ${\displaystyle s\in S^{(t)}}$ ${\displaystyle s\not \in S^{(t)}}$ ${\displaystyle p_{s}=\min(\lambda x_{s}^{*},1)}$ ${\displaystyle x'_{s}}$ ${\displaystyle {\mathcal {U}}^{(t)}}$ ${\displaystyle F}$ ${\displaystyle x^{(t)}}$

${\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 se determina solo después de la iteración . ${\displaystyle E[F|x^{(t)}]}$ ${\displaystyle t}$

Mantener la probabilidad condicional de falla por debajo de 1

Para mantener la probabilidad condicional de falla por debajo de 1, basta con mantener la expectativa condicional de por debajo de 1. Para hacer esto, basta con evitar que la expectativa condicional de aumente. Esto es lo que hará el algoritmo. Se fijará en cada iteración para garantizar que ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle x'_{s}}$

${\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 la iteración th, ¿cómo puede el algoritmo configurarse para garantizar que ? Resulta que puede configurarse simplemente de modo que minimice el valor resultante de . ${\displaystyle t}$ ${\displaystyle x'_{s'}}$ ${\displaystyle E[F|x^{(t)}]\leq E[F|S^{(t-1)}]}$ ${\displaystyle x'_{s'}}$ ${\displaystyle E[F|x^{(t)}]}$

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

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

Dado que un 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, si se configura de forma que se minimice el valor resultante de se garantizará que . Esto es lo que hará el algoritmo. ${\displaystyle x'_{s'}}$ ${\displaystyle E[F|x^{(t)}]}$ ${\displaystyle E[F|x^{(t)}]\leq E[F|x^{(t-1)}]}$

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

${\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 debe establecerse en 0 si esta expresión es positiva y en 1 en caso contrario. Esto da como resultado el siguiente algoritmo. ${\displaystyle x'_{s'}}$

Algoritmo de redondeo aleatorio para la cobertura del conjunto

Entrada: sistema , universo , vector de costos ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {U}}}$ ${\displaystyle c}$

Salida: cobertura del conjunto (una solución al programa lineal entero estándar para cobertura del conjunto) ${\displaystyle x'}$

1. Calcular una cobertura de conjunto fraccionaria de costo mínimo (una solución óptima para la relajación LP). ${\displaystyle x^{*}}$
2. Sea . Sea para cada . ${\displaystyle \lambda \leftarrow \ln(2|{\mathcal {U}}|)}$ ${\displaystyle p_{s}\leftarrow \min(\lambda x_{s}^{*},1)}$ ${\displaystyle s\in {\mathcal {S}}}$
3. Para cada uno haz lo siguiente: ${\displaystyle s'\in {\mathcal {S}}}$
   1. Sea . ( contiene los conjuntos aún no decididos.) ${\displaystyle {\mathcal {S}}\leftarrow {\mathcal {S}}-\{s'\}}$ ${\displaystyle {\mathcal {S}}}$
   2. Si    ${\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _{s\in {\mathcal {S}},s\ni e}(1-p_{s})}$

      Luego establece , ${\displaystyle x'_{s}\leftarrow 0}$

      de lo contrario establezca y . ${\displaystyle x'_{s}\leftarrow 1}$ ${\displaystyle {\mathcal {U}}\leftarrow {\mathcal {U}}-s'}$

        ( contiene los elementos aún no cubiertos). ${\displaystyle {\mathcal {U}}}$

4. Devolver . ${\displaystyle x'}$

Lema (garantía de aproximación para el algoritmo)

El algoritmo anterior devuelve una cobertura de conjunto cuyo costo, en la mayoría de los casos, es el costo mínimo de cualquier cobertura de conjunto (fraccionaria). ${\displaystyle x'}$ ${\displaystyle 2\ln(2|{\mathcal {U}}|)}$

prueba

El algoritmo garantiza que la expectativa condicional de , , no aumente 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 , de esta manera el algoritmo garantiza que la probabilidad condicional de falla se mantenga por debajo de 1. Por lo tanto, al final, cuando se determinan todas las opciones, el algoritmo alcanza un resultado exitoso. Es decir, el algoritmo anterior devuelve una cobertura de conjunto de costo como máximo veces el costo mínimo de cualquier cobertura de conjunto (fraccional). ${\displaystyle F}$ ${\displaystyle E[F\,|\,x^{(t)}]}$ ${\displaystyle F}$ ${\displaystyle x'}$ ${\displaystyle 2\ln(2|{\mathcal {U}}|)}$

Observaciones

En el ejemplo anterior, el algoritmo se guió por la expectativa condicional de una variable aleatoria . En algunos casos, en lugar de una expectativa condicional exacta, se utiliza un límite superior (o, a veces, un límite inferior) para alguna expectativa condicional. Esto se denomina estimador pesimista . ${\displaystyle F}$

Comparación con otras aplicaciones del método probabilístico

El paso de redondeo aleatorio difiere de la mayoría de las aplicaciones del método probabilístico en dos aspectos:

1. La complejidad computacional del paso de redondeo es importante. Debe ser implementable mediante un algoritmo rápido (por ejemplo, de tiempo polinomial ) .
2. La distribución de probabilidad subyacente al experimento aleatorio es una función de la solución de una relajación de la instancia del problema. Este hecho es crucial para probar la garantía de rendimiento del algoritmo de aproximación --- es decir, que para cualquier instancia del problema, el algoritmo devuelve una solución que se aproxima a la solución óptima para esa instancia específica . En comparación, las aplicaciones del método probabilístico en combinatoria muestran típicamente la existencia de estructuras cuyas características dependen de otros parámetros de la entrada. Por ejemplo, considere el teorema de Turán , que puede enunciarse como "cualquier grafo con vértices de grado medio debe tener un conjunto independiente de tamaño al menos . (Véase aquí para una prueba probabilística del teorema de Turán ). Aunque hay grafos para los que este límite es estricto, también hay grafos que tienen conjuntos independientes mucho mayores que . Por lo tanto, el tamaño del conjunto independiente que se muestra que existe según el teorema de Turán en un grafo puede, en general, ser mucho menor que el conjunto independiente máximo para ese grafo. ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle n/(d+1)}$ ${\displaystyle n/(d+1)}$

Véase también

• Método de probabilidades condicionales
• Redondeo aleatorio sin resolver el programa lineal. ^{[4] [5]}

Referencias

1. Raghavan, Prabhakar ; Tompson, Clark D. (1987), "Redondeo aleatorio: una técnica para algoritmos y pruebas algorítmicas demostrablemente buenos", Combinatorica , 7 (4): 365–374, doi :10.1007/BF02579324, S2CID  5749936.
2. Motwani, Rajeev ; Raghavan, Prabhakar (25 de agosto de 1995). Algoritmos aleatorios. Cambridge University Press . ISBN 978-0-521-47465-8.
3. Vazirani, Vijay (5 de diciembre de 2002). Algoritmos de aproximación. Springer Verlag . ISBN 978-3-540-65367-7.
4. Young, Neal E. (2002). "Redondeo aleatorio sin resolver el programa lineal". arXiv : cs/0205036 .
5. Young, Neal. "Redondeo aleatorio inconsciente". AlgNotes . Consultado el 14 de septiembre de 2023 .

• Raghavan, Prabhakar (1988), "Construcción probabilística de algoritmos deterministas: aproximación de programas de empaquetamiento de números enteros", Journal of Computer and System Sciences , 37 (2): 130–143, doi : 10.1016/0022-0000(88)90003-7.

Lectura adicional

• Althöfer, Ingo (1994), "Sobre aproximaciones dispersas a estrategias aleatorias y combinaciones convexas", Álgebra lineal y sus aplicaciones , 199 : 339–355, doi : 10.1016/0024-3795(94)90357-3 , MR  1274423
• Hofmeister, Thomas; Lefmann, Hanno (1996), "Cálculo de aproximaciones dispersas de forma determinista", Álgebra lineal y sus aplicaciones , 240 : 9–19, doi : 10.1016/0024-3795(94)00175-8 , MR  1387283
• Lipton, Richard J.; Young, Neal E. (1994), "Estrategias simples para grandes juegos de suma cero con aplicaciones a la teoría de la complejidad", STOC '94: Actas del vigésimo sexto simposio anual de la ACM sobre teoría de la computación , Nueva York, NY: ACM , págs. 734–740, arXiv : cs.cc/0205035 , doi : 10.1145/195058.195447, ISBN 978-0-89791-663-9, Número de identificación del sujeto  7524887