En informática , un argumento de cobro se utiliza para comparar el resultado de un algoritmo de optimización con una solución óptima. Normalmente se utiliza para demostrar que un algoritmo produce resultados óptimos al probar la existencia de una función inyectiva particular . Para problemas de maximización de beneficios , la función puede ser cualquier mapeo uno a uno de elementos de una solución óptima a elementos del resultado del algoritmo. Para problemas de minimización de costes, la función puede ser cualquier mapeo uno a uno de elementos del resultado del algoritmo a elementos de una solución óptima.
Para que un algoritmo resuelva de forma óptima un problema de maximización de beneficios, el algoritmo debe producir un resultado que tenga tantos beneficios como la solución óptima para cada posible entrada. Sea | A(I) | el beneficio del resultado del algoritmo dado un insumo I , y sea | OPT(I) | el beneficio de una solución óptima para I . Si existe una función inyectiva h : OPT(I) → A(I) , se deduce que | OPT(I) | ≤ | A(I) | . Dado que la solución óptima tiene el mayor beneficio alcanzable, esto significa que el resultado dado por el algoritmo es tan rentable como la solución óptima, y por lo tanto el algoritmo es óptimo.
La corrección del argumento de cobro para un problema de minimización de costos es simétrica. Si | A(I) | y | OPT(I) | denotan el costo de la salida del algoritmo y la solución óptima respectivamente, entonces la existencia de una función inyectiva h : A(I) → OPT(I) significaría que | A(I) | ≤ | OPT(I) | . Dado que la solución óptima tiene el costo más bajo, y el costo del algoritmo es el mismo que el costo de la solución óptima del problema de minimización, entonces el algoritmo también resuelve el problema de manera óptima.
Los argumentos de cobro también se pueden utilizar para mostrar resultados de aproximación. En particular, se pueden utilizar para demostrar que un algoritmo es una aproximación n a un problema de optimización. En lugar de demostrar que un algoritmo produce resultados con el mismo valor de beneficio o coste que la solución óptima, demuestre que alcanza ese valor dentro de un factor de n . En lugar de demostrar la existencia de una función uno a uno, el argumento de cobro se centra en demostrar que existe una función n a uno para demostrar resultados de aproximación.
Dado un conjunto de n intervalos I = {I 1 , I 2 , ... , I n } , donde cada intervalo I i ∈ I tiene un tiempo de inicio s i y un tiempo de finalización f i , donde s i < f i , el objetivo es encontrar un subconjunto máximo de intervalos mutuamente compatibles en I . Aquí, se dice que dos intervalos I j e I k son compatibles si no se superponen, en el sentido de que s j < f j ≤ s k < f k .
Consideremos el algoritmo codicioso de tiempo de finalización más temprano , descrito de la siguiente manera:
El problema de programación por intervalos puede considerarse como un problema de maximización de beneficios, en el que la cantidad de intervalos en el subconjunto mutuamente compatible es el beneficio. El argumento de cobro puede utilizarse para demostrar que el algoritmo de tiempo de finalización más temprano es óptimo para el problema de programación por intervalos.
Dado un conjunto de intervalos I = {I 1 , I 2 , ... , I n } , sea OPT(I) cualquier solución óptima del problema de programación de intervalos, y sea EFT(I) la solución del algoritmo de tiempo de finalización más temprano. Para cualquier intervalo J ∈ OPT(I) , defina h(J) como el intervalo J' ∈ EFT(I) que interseca a J con el tiempo de finalización más temprano entre todos los intervalos en EFT(I) que intersecan a J . Para demostrar que el algoritmo de tiempo de finalización más temprano es óptimo utilizando el argumento de cobro, se debe demostrar que h es una función biunívoca que asigna intervalos en OPT(I) a aquellos en EFT(I) . Suponga que J es un intervalo arbitrario en OPT(I) .
Demuestre que h es una función que asigna OPT(I) a EFT(I) .
Demuestre que h es uno a uno.
Por lo tanto, h es una función biunívoca que asigna intervalos en OPT(I) a los de EFT(I) . Según el argumento de cobro, el algoritmo de tiempo de finalización más temprano es óptimo.
Consideremos el problema de programación de intervalos de trabajo, una variante NP-hard del problema de programación de intervalos visitado anteriormente. Como antes, el objetivo es encontrar un subconjunto máximo de intervalos mutuamente compatibles en un conjunto dado de n intervalos, I = {I 1 , I 2 , ... , I n } . Cada intervalo I i ∈ I tiene un tiempo de inicio s i , un tiempo de finalización f i y una clase de trabajo c i . Aquí, se dice que dos intervalos I j e I k son compatibles si no se superponen y tienen clases diferentes.
Recordemos el algoritmo de tiempo de finalización más temprano del ejemplo anterior. Después de modificar la definición de compatibilidad en el algoritmo, el argumento de cobro se puede utilizar para demostrar que el algoritmo de tiempo de finalización más temprano es un algoritmo de 2 aproximaciones para el problema de programación de intervalos de trabajo.
Sean OPT(I) y EFT(I) la solución óptima y la solución producida por el algoritmo de tiempo de finalización más temprano, como se definió anteriormente. Para cualquier intervalo J ∈ OPT(I) , defina h de la siguiente manera:
Para demostrar que el algoritmo de tiempo de finalización más temprano es un algoritmo de 2 aproximaciones que utiliza el argumento de cobro, se debe demostrar que h es una función dos a uno que asigna intervalos en OPT(I) a aquellos en EFT(I) . Suponga que J es un intervalo arbitrario en OPT(I) .
Demuestre que h es una función que asigna OPT(I) a EFT(I) .
Demuestre que h es dos a uno.
Por lo tanto, h no asigna más de dos intervalos distintos en OPT(I) al mismo intervalo en EFT(I) , y por lo tanto h es dos a uno. Según el argumento de cobro, el algoritmo de tiempo de finalización más temprano es un algoritmo de dos aproximaciones para el problema de programación de intervalos de trabajo.
