En informática , se utiliza un argumento de carga para comparar la salida de un algoritmo de optimización con una solución óptima. Por lo general, se usa para mostrar que un algoritmo produce resultados óptimos al probar la existencia de una función inyectiva particular . Para problemas de maximización de ganancias , la función puede ser cualquier mapeo uno a uno de elementos de una solución óptima a elementos de la salida del algoritmo. Para problemas de minimización de costos, la función puede ser cualquier mapeo uno a uno de los elementos de la salida del algoritmo a los elementos de una solución óptima.
Para que un algoritmo resuelva de manera óptima un problema de maximización de ganancias, el algoritmo debe producir una salida que tenga tanta ganancia como la solución óptima para cada entrada posible. Dejar | A(yo) | denote la ganancia de la salida del algoritmo dada una entrada I , y sea | OPT(I) | denote el beneficio de una solución óptima para I . Si existe una función inyectiva h : OPT(I) → A(I) , se sigue que | OPT(I) | ≤ | A(yo) |. Dado que la solución óptima tiene la mayor ganancia posible, esto significa que la salida proporcionada por el algoritmo es tan rentable como la solución óptima, por lo que el algoritmo es óptimo.
La corrección del argumento de cobro para un problema de minimización de costos es simétrica. Si | A(yo) | y | OPT(I) | denotemos 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(yo) | ≤ | 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 carga también se pueden usar para mostrar resultados de aproximación. En particular, se puede usar para mostrar que un algoritmo es una aproximación n a un problema de optimización. En lugar de mostrar que un algoritmo produce salidas con el mismo valor de beneficio o costo que la solución óptima, demuestre que alcanza ese valor dentro de un factor de n . En lugar de probar la existencia de una función uno a uno, el argumento de la carga se enfoca en probar que existe una función n a uno para probar los resultados de la aproximación.
Dado un conjunto de n intervalos I = {I 1 , I 2 , ... , I n } , donde cada intervalo I i ∈ I tiene un tiempo inicial s i y un tiempo final 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 .
El problema de programación de intervalos puede verse como un problema de maximización de beneficios, donde el número de intervalos en el subconjunto mutuamente compatible es el beneficio. El argumento de cobro se puede usar para mostrar que el algoritmo de tiempo de finalización más temprano es óptimo para el problema de programación de intervalos.