Se sabe que Ford-Fulkerson o Edmonds-Karp con la heurística del tubo de grasa (dos algoritmos para flujo máximo) no necesitan detenerse si algunos de los pesos son irracionales. De hecho, ¡incluso pueden converger en el valor incorrecto ! Sin embargo, todos los ejemplos que pude encontrar en la literatura [referencias a continuación, más las referencias allí] usan un solo valor irracional: la relación dorada conjugada , y otros valores que son racionales o son múltiplos racionales de . Mi pregunta principal es:ϕ′
Pregunta general: ¿Qué sucede con otros valores irracionales?
Por ejemplo (pero no sienta que tiene que responder todo esto para publicar, me gustaría encontrar una respuesta interesante para cualquiera u otras preguntas que se encuentren dentro de la pregunta general anterior):
Dado cualquier , ¿se puede construir (o incluso mostrar la existencia de) tales contraejemplos?
Más débilmente: ¿hay ejemplos conocidos que usen un valor irracional esencialmente diferente de ? Es decir, ¿hay algún que no sea un múltiplo racional de (o más fuertemente no en ) y tal que haya contraejemplos de Ford-Fulkerson y / o Edmonds- ¿Karp donde se encuentran todos los pesos en ? α ϕ ′ Q ( ϕ ′ ) Q ( α )
En la otra dirección, ¿existe un irracional tal que Ford-Fulkerson (resp., Edmonds-Karp) se detenga con el valor correcto en todos los gráficos cuyos pesos provienen de ? (¿O más fuerte, de ?)Q ( α )
En todos los casos, quiero asumir algo como el modelo RAM real, para que la aritmética exacta y las comparaciones exactas de números reales se realicen en tiempo constante.
(Hay otros algoritmos de flujo máximo que se sabe que se ejecutan en un tiempo muy polinómico, incluso con pesos reales arbitrarios, lo que quizás sea la razón por la cual este tipo de pregunta puede no haber sido explorada más a fondo. Pero habiendo enseñado estos algoritmos en mi clase de algoritmos de pregrado Todavía tengo curiosidad por esto.)
Referencias
Zwick TCS 1999 dio un contraejemplo mínimo para Ford-Fulkerson.
Queyranne o Queyranne Math dieron un contraejemplo para Edmonds-Karp . Oper Res. 1980 , aunque no sé si ese es mínimo.
Ambos se pueden encontrar en las notas de clase de Jeff Erickson , con el primero en la Sección 23.5 y el segundo como el Ejercicio 14 de la Clase 23.
fuente