¿Para qué algoritmos hay una gran brecha entre el análisis teórico y la realidad?

52

Dos formas de analizar la eficiencia de un algoritmo son

  1. poner un límite superior asintótico en su tiempo de ejecución, y
  2. para ejecutarlo y recopilar datos experimentales.

Me pregunto si hay casos conocidos en los que haya una brecha significativa entre (1) y (2). Con esto quiero decir que (a) los datos experimentales sugieren un asintótico más estricto o (b) existen algoritmos X e Y, de modo que el análisis teórico sugiere que X es mucho mejor que Y y los datos experimentales sugieren que Y es mucho mejor que X.

Dado que los experimentos generalmente revelan un comportamiento de caso promedio, espero que las respuestas más interesantes se refieran a los límites superiores de caso promedio. Sin embargo, no quiero descartar posibles respuestas interesantes que hablan de diferentes límites, como la respuesta de Noam sobre Simplex.

Incluir estructuras de datos. Por favor, ponga un algo / ds por respuesta.

Radu GRIGore
fuente
Sería útil si aclaras de qué tipo de límites superiores estás hablando. ¿Solo está hablando de problemas para los cuales hay una brecha significativa entre los límites superior e inferior más conocidos para la complejidad del tiempo en el peor de los casos? ¿O también incluye problemas para los que se conocen límites estrechos en el peor de los casos, pero los tiempos de ejecución típicos son significativamente más rápidos? Puede ser más interesante considerar la complejidad suavizada en lugar de la complejidad del peor de los casos. Los resultados experimentales en entradas "típicas" o entradas aleatorias hacen poco para refutar la existencia de entradas patológicas.
James King el
En ese caso, creo que hay dos preguntas que deberían hacerse por separado: una sobre las brechas entre la complejidad del caso más desfavorable y la complejidad del caso promedio / suavizado, y otra sobre las brechas entre la complejidad del caso promedio teórico / suavizado y los resultados experimentales prácticos. Editar: hiciste una edición abordando esto mientras escribía mi comentario :)
James King

Respuestas:

37

El ejemplo más deslumbrante es, por supuesto, el método Simplex que se ejecuta rápidamente en la práctica, sugiriendo poli-timeness, pero lleva un tiempo exponencial en teoría. Dan Spielman acaba de recibir el premio Nevanlinna en gran medida por explicar este misterio.

En términos más generales, muchas instancias de programación de enteros se pueden resolver bastante bien utilizando solucionadores de IP estándar, por ejemplo, se podrían resolver subastas combinatorias para la mayoría de las distribuciones intentadas en entradas de tamaño significativo: http://www.cis.upenn.edu/~mkearns /teaching/cgt/combinatorial-auctions-survey.pdf

Noam
fuente
3
¿Se ha encontrado una familia explícita de programas lineales para los cuales el simplex toma tiempo exponencial?
Optar
1
Según tengo entendido, hay muchas familias explícitas que requieren un tiempo exponencial (por ejemplo, la primera señal dada por Klee y Minty: "¿Qué tan bueno es el algoritmo simplex?", 1972). Sin embargo, la elección de la regla de pivote es relevante para estos resultados. Supongo que la mayoría de las referencias a estos resultados se pueden encontrar en el artículo de Spielman y Teng ( arxiv.org/abs/cs/0111050 ).
MRA
hay límites inferiores para alguna regla de pivote específica en este documento cs.au.dk/~tdh/papers/random_edge.pdf
Igor Shinkar
26

Bases Groebner . El peor tiempo de ejecución es doblemente exponencial (en el número de variables). Sin embargo, en la práctica, especialmente para problemas bien estructurados, los algoritmos F4 y F5 son efectivos (es decir, terminan bastante rápido). Todavía es un área activa de investigación para determinar cuál debería ser la conjetura adecuada incluso con respecto al tiempo de ejecución promedio o esperado. Se conjetura que está relacionado, de alguna manera, con el volumen del politopo de Newton del ideal subyacente.

Jacques Carette
fuente
¿Promedio / esperado bajo qué distribución? Pensé que incluso definir el tiempo de ejecución esperado era difícil para los problemas algebraicos ...
Joshua Grochow
1
No sé para los casos resueltos rápidamente por los métodos F4 y F5, pero es bastante fácil construir un sistema de polinomios con muchas variables y bajo grado que codifiquen una instancia SAT. En tal caso, no sé que el algoritmo supera a DPLL / DPLL +. ¡Realmente me gustaría saber más sobre los resultados experimentales de estas cosas!
MassimoLauria
@Joshua: en este punto, cualquier distribución que permita resultados ... @Massimo: ¡codificar el problema X como una instancia de Y casi nunca supera a los algoritmos especializados para X! Pero GB y DPLL son esencialmente equivalentes, por lo que me sorprendería aún más ver una diferencia efectiva.
Jacques Carette
1
@ Massimo: Sí, el cálculo de GB es NP-Hard. Dependiendo de la formulación. De hecho, la mayoría de las preguntas (finalización, membresía ideal, campo cerrado algebraicamente vs booleanos) son PSPACE completo o peor (EXPSPACE completo). Es decir, se espera que los cálculos de GB sean mucho más difíciles que los problemas de NP completo (y, por lo tanto, incluso en el caso promedio, cualquier algoritmo para ellos como F5 probablemente no superará a DPLL).
Mitch
22

O(2((nortelosolnorte)))

No sé si hay un resultado formal en la complejidad promedio / suavizada del problema, pero recuerdo haber leído que existía, tal vez alguien más pueda sonar para señalar un resultado formal. Ciertamente, hay una gran cantidad de evidencia experimental y muchos solucionadores rápidos. También tengo curiosidad si esta propiedad se extiende a otros miembros de la familia completa de IG.

Anand Kulkarni
fuente
1
O(2norteIniciar sesiónnorte)
2
Oh! Tal vez esté pensando en Babai-Kucera, que ofrece un algoritmo de caso promedio de tiempo lineal para IG: doi.ieeecomputersociety.org/10.1109/SFCS.1979.8
Joshua Grochow
¡Sí, Babai-Kucera es el indicado! Gracias por la referencia
Anand Kulkarni el
20

De David Johnson, una discrepancia en las relaciones de aproximación teórica versus experimental: El problema del vendedor ambulante: un estudio de caso en optimización local, DS Johnson y LA McGeoch . En este artículo, proporcionan evidencia experimental de asintóticos (¡ya que los experimentos alcanzan un tamaño de N = 10,000,000!) Que desafían los asintóticos teóricos: el algoritmo "Greedy" o "Multi-Fragment" de Jon Bentley (relación de aproximación en el peor de los casos al menos logN / loglogN) supera la inserción más cercana y la MST doble, las cuales tienen relaciones de aproximación de 2 en el peor de los casos.

Joshua Grochow
fuente
20

Otro ejemplo que no se ha entendido bien hasta hace poco es el tiempo de ejecución del algoritmo k-means de Lloyd , que (desde un punto de vista práctico) ha sido el algoritmo de agrupamiento elegido por más de 50 años. Recientemente, en 2009, se demostró (por Vattani ) que, en el peor de los casos, el algoritmo de Lloyd requiere una serie de iteraciones que es exponencial en el número de puntos de entrada. Por otro lado, al mismo tiempo, un análisis suavizado (por Arthur, Manthey y Röglin ) demostró que el número suavizado de iteraciones es meramente polinomial, lo que explica el rendimiento empírico.

MRA
fuente
10

Los corolarios transversales, de deque y divididos de la conjetura de la optimización dinámica para árboles de separación son ejemplos de tales brechas. Los experimentos respaldan la afirmación del tiempo lineal, pero no hay pruebas conocidas.

Radu GRIGore
fuente
3
Seth Pettie demostró que las operaciones n deque no requieren más que el tiempo O (n alpha * (n)), donde "alpha *" es la función inversa inversa de Ackermann, que es un espacio bastante pequeño.
jbapple
9

Hay un pequeño problema con la pregunta. De hecho, hay más de dos formas de analizar un algoritmo, y una de las formas teóricas que se ha descuidado es el tiempo de ejecución esperado, en lugar del peor tiempo de ejecución. Es realmente este comportamiento de caso promedio lo que es relevante para hacer experimentos. Aquí hay un ejemplo muy simple: imagine que tiene un algoritmo para una entrada de tamaño n, que toma tiempo n para cada entrada posible de tamaño n, excepto para una entrada específica de cada longitud que lleva tiempo 2 ^ n. Escuche que el peor tiempo de ejecución es exponencial, pero el caso promedio es [(2 ^ n -1) n + (2 ^ n) 1] / (2 ^ n) = n - (n-1) / 2 ^ n que límites a n. Claramente, los dos tipos de análisis dan respuestas muy diferentes, pero esto es de esperarse ya que estamos calculando diferentes cantidades.

Al ejecutar el experimento varias veces, incluso si tomamos el tiempo de ejecución más largo para la muestra, todavía solo estamos muestreando una pequeña porción del espacio de posibles entradas, por lo que si las instancias difíciles son raras, es probable que las perdamos .

Es relativamente fácil construir tal problema: si los primeros n / 2 bits son todos cero, entonces resuelva la instancia 3SAT codificada con los últimos n / 2 bits. De lo contrario rechazar. A medida que n aumenta, el problema tiene aproximadamente el mismo tiempo de ejecución en el peor de los casos que el algoritmo más eficiente para 3SAT, donde el tiempo de ejecución promedio es muy bajo.

Joe Fitzsimons
fuente
Ya respondí a James King anteriormente que espero que las respuestas más interesantes sean sobre el tiempo de ejecución esperado. Editaré la pregunta para que esto sea más visible.
Radu GRIGore
9

La inferencia de tipo Damas-Milner se ha demostrado completa por tiempo exponencial, y hay casos fáciles de construir con explosión exponencial en el tamaño de un resultado. Sin embargo, en la mayoría de las entradas del mundo real se comporta de manera efectivamente lineal.

sclv
fuente
¿Hay alguna referencia que recomendarías para este resultado? Me gustaría leer más al respecto.
Radu GRIGore
1
No lo he leído yo mismo, pero el artículo más frecuentemente citado es Harry G. Mairson, "La capacidad de determinación de la tipificación ML está completa por tiempo exponencial determinista", 17º Simposio sobre Principios de Lenguajes de Programación (1990).
sclv
9

El PTAS para el árbol de Steiner en gráficos planos tiene una dependencia ridícula del épsilon. Sin embargo, hay una implementación que muestra un rendimiento sorprendentemente bueno en la práctica.

zotachidil
fuente
8

Emparejamiento de montones, desde [1]: implementan montones, donde insertar y fusionar tienen O (log n) complejidad amortizada, pero se conjetura que son O (1). En la práctica, son extremadamente eficientes, especialmente para usuarios de fusión.

Los descubrí hoy mientras leía la Sec. 5.5 del libro de C. Okasaki "Estructuras de datos puramente funcionales", así que pensé que debería compartir información sobre ellos.

[1] Fredman, ML, Sedgewick, R., Sleator, DD y Tarjan, RE 1986. El montón de emparejamiento: una nueva forma de montón autoajustable. Algorithmica 1, 1 (enero de 1986), 111-129. DOI = http://dx.doi.org/10.1007/BF01840439

Blaisorblade
fuente
Ha habido algunos avances desde Okasaki, y ahora hay montones (imperativos) de emparejamiento con O (0) meld, O (1) insert and findMin, O (lg lg n) disminuciónKey y O (lg n) deleteMin: arxiv. org / abs / 0903.4130 . Este montón utiliza un mecanismo de emparejamiento diferente que los montones de emparejamiento originales de Fredman et al.
jbapple
7

Relacionado con el comentario de ilyaraz sobre rama y atado, Pataki et al. demuestre que la reducción de la base de la rama y el límite más la red puede resolver casi todas las IP aleatorias en polytime.

Marco
fuente
6

La heurística de Lin-Kernighan para el TSP ("Una heurística efectiva para el problema del vendedor ambulante", Operations Research 21: 489–516, 1973) es muy exitosa en la práctica, pero aún carece de un análisis de caso medio o suavizado para explicar su desempeño. . Por el contrario, Matthias Englert, Heiko Röglin y Berthold Vöcking (Algorithmica, por aparecer) analizan la heurística de 2 opciones para el TSP.

Bodo Manthey
fuente
5

Existen muchos algoritmos muy rápidos y eficientes en la práctica de ramificación y unión para diferentes problemas NP-hard que no podemos analizar rigurosamente: TSP, árbol Steiner, empaquetado de contenedores, etc.

Ω(nortemetro)

revs ilyaraz
fuente
¿Te refieres a O (mn), o estoy confundido?
Radu GRIGore
O(nortemetrolosol(norte2/ /metro))