¿Consecuencias de la existencia de un algoritmo fuertemente polinómico para la programación lineal?

Uno de los santos griales del diseño de algoritmos es encontrar un algoritmo fuertemente polinómico para la programación lineal, es decir, un algoritmo cuyo tiempo de ejecución está limitado por un polinomio en el número de variables y restricciones y es independiente del tamaño de la representación de los parámetros (suponiendo aritmética de costo unitario). ¿Resolver esta pregunta tendría implicaciones fuera de mejores algoritmos para la programación lineal? Por ejemplo, ¿la existencia / no existencia de tal algoritmo tendría alguna consecuencia para la geometría o la teoría de la complejidad?

Editar: Tal vez debería aclarar lo que quiero decir con consecuencias. Busco consecuencias matemáticas o resultados condicionales, las consecuencias que se sabe que es verdad ahora . Por ejemplo: "un algoritmo polinomial para LP en el modelo BSS separaría / colapsaría las clases de complejidad algebraica FOO y BAR", o "si no hay un algoritmo polinomial fuerte, entonces resuelve tal o cual conjetura sobre los politopos", o "a algoritmo fuertemente polinomial para el problema X que puede formularse como un LP tendría una consecuencia interesante bla ". La conjetura de Hirsch sería un buen ejemplo, excepto que solo se aplica si simplex es polinomial.

ds.algorithms conditional-results linear-programming computing-over-reals simplex Ian
fuente

Tampoco hace falta decir que la técnica de prueba utilizada para mostrar este resultado podría ser aún más interesante que el resultado en términos de impacto a largo plazo.

Suresh Venkat

Respuestas:

Esto demostraría que los juegos de paridad y rentabilidad media están en P. Ver Sven Schewe. Desde juegos de paridad y pago hasta programación lineal. MFCS 2009.

Rahul Savani
fuente

excelente. Desearía poder darle a esto más de un +1. Este es un resultado muy bueno.

Suresh Venkat

¿Podría alguien explicar cómo un algoritmo fuertemente polinómico para LP implicaría esto? Schewe construye una instancia de LP de tamaño polinómico con números doblemente exponencialmente grandes. Multa. Ahora ejecutamos el algoritmo de tiempo fuertemente polinómico en él. Pero, ¿no necesitamos simular las operaciones aritméticas que realiza este algoritmo? ¿Cómo se hace esta simulación sin pasar tiempo superpolinomial? (recuerde que los números son doblemente exponenciales; supongo que uno podría hacer el truco del resto chino, pero ¿podemos hacer una comparación de los números de esta manera en el tiempo polinómico?).

Slimton

Z_{2}

$\mathbb{Z}_2$

R

$\mathbb{R}$

Aclaración a mi comentario anterior: si hay un algoritmo fuertemente polinómico para LP, entonces es polinomial en el modelo BSS, en cuyo caso el artículo implica paridad y los juegos de pago también están en P en el modelo BSS.

Ian

@ Ian: En otras palabras: esta respuesta fue un poco engañosa (pero eso no te impidió aceptarla como respuesta válida).

slimton

$(d n)^{Ackerman(10000)}$ ) el algoritmo elipsoide, por ejemplo, además de su significado teórico, condujo (?) al desarrollo del método de punto interior, que en algunos casos fue más rápido que el algoritmo simplex. Esto condujo a una aceleración significativa en la práctica, ya que ambos enfoques se redujeron al límite máximo de lo que se puede hacer.

Sariel Har-Peled
fuente

Pero estas condiciones son válidas para casi cualquier resultado teórico: puede o no ser útil dependiendo del tiempo de ejecución, y las técnicas / ideas en el resultado pueden conducir a avances futuros.

Ian

Realmente no. Si alguna forma de la conjetura de Hirsch es cierta, y la prueba es constructiva, entonces seguramente conduciría a soluciones más rápidas para LP. En resumen, si la pregunta es específica, entonces sus implicaciones son claras, y si la pregunta es amplia, entonces podría conducir a nada. O dicho de otra manera, la única consecuencia segura del algoritmo de tiempo polinómico para LP es que entenderíamos el problema mejor de lo que lo hacemos ahora.

Sariel Har-Peled

Aquí hay una consecuencia para la geometría: un enlace fuertemente polinomial para cualquier variante (aleatorio o determinista) del algoritmo simplex implica un enlace polinomial en el diámetro de cualquier gráfico de politopo. Esto implica que la "versión polinomial" de la conjetura de Hirsch es verdadera.

Shiva Kintali
fuente

pero no hay razón para creer que un algoritmo de tiempo fuertemente polinómico para LPs tenga que pasar por el método simplex. Los métodos más conocidos hasta ahora (subexponencial) utilizan una estrategia de muestreo aleatorio + recursividad.

Suresh Venkat

Ups Perdí el punto.

Shiva Kintali el

Esto solo se cumple si simplex es fuertemente polinomial. Estoy buscando resultados que se mantengan de manera más general. Puede ser que la conjetura polinómica de Hirsch sea falsa pero que otro algoritmo sea fuertemente polinomial, o que la conjetura polinómica de Hirsch sea verdadera pero simplex sea exponencial porque no puede encontrar un camino corto en el tiempo polinómico.

Ian

@Suresh: En realidad, estoy bastante seguro de que el muestreo aleatorio subexponencial + la estrategia de recursión que mencionas (Clarkson-Matoušek-Sharir-Welzl / Kalai, ¿verdad?) Es un algoritmo dual simplex. (Pero esto no contradice su punto.)

Jeff el

Oh espera. ¿Michael Goldwasser no lo resolvió hace mucho tiempo en un artículo de SIGACT? Hmm ahora tengo que ir a cavar.

Suresh Venkat