Algoritmos de aproximación utilizados en algoritmos exactos.

Los algoritmos de aproximación pueden dar salida hasta algún factor constante. Esto es un poco menos satisfactorio que los algoritmos exactos.

Sin embargo, los factores constantes se ignoran en la complejidad del tiempo.

Entonces, me pregunto si el siguiente truco es posible o si fue utilizado, para resolver algún problema :$B \circ A$

1. Use un algoritmo de aproximación para resolver el problema para obtener la solución dentro del factor constante;$A$$S$
2. Use un algoritmo exacto para resolver el problema , cuyo tiempo de ejecución depende del peso de pero funciona siempre que sea ​​una solución correcta.$B$$S$$S$

De esta manera, la aproximación es un "subprocedimiento" de un algoritmo exacto, y el factor constante perdido en el paso 1 se traga en el paso 2.

Un ejemplo de la complejidad parametrizada es una kernelización para el problema de la cubierta de vértices utilizando un teorema de Nemhauser y Trotter.

En el problema de cobertura de vértice mínimo, se nos da un gráfico G no dirigido, y necesitamos encontrar una cubierta de vértice de G de tamaño mínimo. Una cubierta de vértice de un gráfico no dirigido es un subconjunto de vértice que toca todos los bordes.

Aquí hay un algoritmo exacto que usa una aproximación en la primera fase.

Fase 1: Configure la formulación de programación lineal entera del problema de cobertura de vértice mínimo . Se sabe (o es fácil de mostrar) que una solución óptima básica de la relajación de la programación lineal es semi integral (es decir, cada coordenada es 0, 1 o 1/2). Tal solución óptima básica se puede encontrar mediante un algoritmo de tiempo polinomial habitual para programación lineal (o en este caso especial, podemos formularlo como un problema de flujo de red, por lo que podemos resolverlo combinatoriamente en tiempo polinomial). Al tener una solución óptima tan básica, la redondeamos para obtener una solución factible al problema original de programación lineal de enteros. Sea S el subconjunto de vértices correspondiente. Es bueno tener en cuenta que S es una aproximación 2 de la instancia de cobertura de vértice mínima dada.

Fase 2: Encuentre una cobertura mínima de vértice en el subgrafo inducido por S (por ejemplo, mediante una búsqueda exhaustiva). Un teorema de Nemhauser y Trotter establece que este subgrafo contiene una solución óptima del gráfico de entrada original. Entonces, la corrección de este enfoque sigue.

Puede consultar un libro de Niedermeier sobre algoritmos de parámetros fijos para este algoritmo.

Un ejemplo está relacionado con descomposiciones de árboles y gráficos de pequeño ancho de árbol.

Por lo general, si se nos da una descomposición de árbol, es bastante sencillo aplicar programación dinámica para resolver un problema gráfico forma óptima. El tiempo de ejecución depende del ancho de la descomposición del árbol.$B$

Sin embargo, generalmente no se nos da una descomposición del árbol, pero necesitamos encontrarla. Para resolver el problema lo más rápido posible, nos gustaría encontrar un árbol de la descomposición de la anchura más pequeña posible - ahora esto es nuestro problema .$B$$A$

Podríamos tratar de resolver el problema exactamente, pero entonces podríamos perder demasiado tiempo en la parte . Una posible solución es utilizar un algoritmo de aproximación por parte . A continuación, parte es más rápido, a un costo de garantías de tiempo de funcionamiento peores en la parte .$A$$A$$A$$A$$B$

Otro ejemplo está relacionado con los compiladores y la asignación de registros . Supongamos que hemos implementado un algoritmo exacto que resuelve un problema en tiempo polinómico. El tiempo de ejecución del algoritmo depende, en parte, de lo bien que el compilador logrado Asignar variables en registros de la CPU - este es nuestro problema .$B$$A$

La solución del problema es correcta incluso si el compilador usa un algoritmo de aproximación para resolver el problema ; Sin embargo, un factor de aproximación en el problema afecta el tiempo de ejecución del algoritmo .$B$$A$$A$$B$

Un ejemplo de un algoritmo de aproximación que converge a la solución exacta sería el algoritmo elipsoide para resolver LP: si los coeficientes son racionales, entonces se puede calcular una distancia mínima entre dos vértices del politopo factible. Ahora, el algoritmo elipsoide calcula repetidamente un elliposoide cada vez más pequeño que debe contener la solución óptima. Una vez que el elliposoide es lo suficientemente pequeño como para contener solo un vértice único, esencialmente encuentra el vértice óptimo. Es por eso que LP es débilmente polinomial.

En cuanto a un ejemplo más cercano a su esquema, considere el algoritmo de Matousek para encontrar el disco más pequeño que contenga puntos en el plano. El algoritmo primero encuentra una aproximación de 2 (en el radio), divide el plano en la cuadrícula apropiada y resuelve el problema dentro de cada grupo de cuadrícula exactamente, usando un algoritmo lento. $k$

Finalmente, ir más allá de un campo, muchos algoritmos que siguen la técnica de alteración (tomar una muestra aleatoria, y luego hacer algunas reparaciones para obtener lo que desea) se encuadra en dicho marco. Un lindo ejemplo es el algoritmo para calcular la mediana usando muestreo aleatorio (ver el libro de Motwani y Raghavan). Hay muchos ejemplos de este tipo: podría decirse que muchos de los algoritmos incrementales aleatorios en Geometría Computacional se incluyen en este marco.

Muchos algoritmos sensibles a la salida emplean esta técnica. Por ejemplo, aquí hay un problema simple en el que se puede usar esta técnica:

Problema . Se le proporciona una matriz A [1 .. n ] en la que cada elemento está a k posiciones de distancia de la posición en la que habría estado si A estuviera ordenado.

Por ejemplo, A [1..7] que se muestra a continuación podría ser una matriz de entrada para k = 2.

Fuente del problema: Algo Muse Archive.