Recientemente he leído algunas cosas sobre problemas de optimización incremental, pero no puedo ver cuál es la diferencia entre esos y los problemas de optimización en línea. Mi impresión es que puedo definir cada problema en línea como una contraparte incremental (lo contrario es claramente cierto).
Aquí van las definiciones (no muy formales). En un problema incremental, uno recibe una secuencia de instancias de un problema de optimización. La instancia (i + 1) -th es una "extensión" de la i-th. La solución (i + 1) -th debe calcularse sin conocimiento de las instancias "futuras", y debe mantener las decisiones tomadas en la solución i-th. El ejemplo clásico es con el problema k-mediano: después de abrir k instalaciones, uno quiere tener k '> k instalaciones pero no quiere demoler las antiguas.
En un problema en línea, (la definición habitual es esa) se le da a uno una secuencia de "solicitudes". Aquí, uno también tiene que responder una solicitud sin conocer las solicitudes futuras. Uno quiere optimizar el costo / ganancia de responder la secuencia como un todo.
Creo que para cualquier problema en línea puedo definir un problema de optimización "fuera de línea" que se ajuste a la definición incremental (y lo que generalmente veo es lo contrario). Si las definiciones son equivalentes, ¿de qué sirve usar un nombre diferente para el mismo concepto?
fuente
Respuestas:
Esto se discute en la sección 2.2.3 de la tesis de Jeffrey Hartline: http://www.cs.cornell.edu/w8/~jhartlin/finaldiss.pdf
Los problemas en línea tienen que ver con la incertidumbre informativa: no sabes qué entradas vendrán mañana, y la dificultad suele ser la información teórica, no computacional. Por otro lado, no hay incertidumbre en un problema de optimización incremental como lo define Hartline: cada parámetro del problema se conoce desde el principio. Sin restricciones computacionales, los problemas siempre se pueden resolver de manera óptima.
Entonces, tal vez su definición sea incorrecta, ya que la suya parece un problema en línea. El problema de la "optimización incremental" parece estar definido en esta tesis de 2008, y difiere de su definición en que no hay incertidumbre.
fuente