Argumento de acusación

Dado un conjunto de n intervalos I = {I ₁ , I ₂ , ... , 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 maximal de intervalos mutuamente compatibles en I . Aquí, se dice que dos intervalos I _j e I _k son compatibles si no se superponen, es decir, s _j < f _j ≤ s _k < f _k .

Consideremos el algoritmo voraz de tiempo de finalización más temprano , descrito de la siguiente manera:

• Comience con un conjunto vacío de intervalos.
• Ordena los intervalos en I por tiempos de finalización ascendentes.
• Consideremos cada intervalo de I ordenado. Añadamos el intervalo al conjunto si no entra en conflicto con ningún intervalo que ya esté contenido en él. De lo contrario, descartemos el intervalo.

El problema de la programación de intervalos puede considerarse un problema de maximización de beneficios, donde el número de intervalos en el subconjunto compatible entre sí representa el beneficio. El argumento de tarificación puede utilizarse para demostrar que el algoritmo de tiempo de finalización más temprano es óptimo para el problema de la programación de intervalos.

Dado un conjunto de intervalos I = {I ₁ , I ₂ , ... , 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 carga, se debe demostrar que h es una función biyectiva que mapea los 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 mapea OPT(I) a EFT(I) .

Supongamos, por contradicción, que no existe ningún intervalo J' ∈ EFT(I) que satisfaga h(J) = J' . Por definición de h , esto significa que ningún intervalo en EFT(I) interseca con J. Sin embargo, esto también significaría que J es compatible con todos los intervalos en EFT(I) , por lo que el algoritmo de tiempo de finalización más temprano habría añadido J a EFT(I) , y por lo tanto J ∈ EFT(I) . Surge una contradicción, ya que se supuso que J no interseca con ningún intervalo en EFT(I) , pero J está en EFT(I) , y J interseca consigo mismo. Por lo tanto, por contradicción, J debe intersecar con al menos un intervalo en EFT(I) .

Resta demostrar que h(J) es único. Según la definición de compatibilidad, dos intervalos compatibles nunca pueden tener el mismo tiempo de finalización. Dado que todos los intervalos en EFT(I) son mutuamente compatibles, ninguno de ellos tiene el mismo tiempo de finalización. En particular, cada intervalo en EFT(I) que interseca con J tiene tiempos de finalización distintos, por lo que h(J) es único.

Demuestra que h es inyectiva.

Supongamos, por contradicción, que h no es inyectiva. Entonces hay dos intervalos distintos en OPT(I) , J ₁ y J ₂ , tales que h mapea tanto J ₁ como J ₂ al mismo intervalo J' ∈ EFT(I) . Sin pérdida de generalidad, supongamos que f ₁ < f _2. Los intervalos J ₁ y J ₂ no pueden intersecarse porque ambos están en la solución óptima, por lo que f ₁ ≤ s ₂ < f _2. Dado que EFT(I) contiene J' en lugar de J ₁ , el algoritmo de tiempo de finalización más temprano encontró J' antes que J _1. Por lo tanto, f' ≤ f _1. Sin embargo, esto significa que f' ≤ f ₁ ≤ s ₂ < f ₂ , por lo que J' y J ₂ no se intersecan. Esto es una contradicción porque h no puede mapear J ₂ a J' si no se intersecan. Por lo tanto, por contradicción, h es inyectiva.

Por lo tanto, h es una función biyectiva que asigna intervalos en OPT(I) a aquellos en EFT(I) . Según el argumento de carga, 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-difícil del problema de programación de intervalos que vimos anteriormente. Como antes, el objetivo es encontrar un subconjunto máximo de intervalos mutuamente compatibles en un conjunto dado de n intervalos, I = {I ₁ , I ₂ , ... , 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. Tras modificar la definición de compatibilidad en el algoritmo, el argumento de carga puede utilizarse para demostrar que el algoritmo de tiempo de finalización más temprano es un algoritmo de aproximación 2 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 definieron anteriormente. Para cualquier intervalo J ∈ OPT(I) , defina h de la siguiente manera:

${\displaystyle h(J)={\begin{cases}{\mbox{el intervalo en EFT(I) con la misma clase de trabajo que J, si existe}}\\{\mbox{el intervalo con el tiempo de finalización más temprano entre todos los intervalos en EFT(I) que intersecan J, en caso contrario}}\end{cases}}}$

Para demostrar que el algoritmo de tiempo de finalización más temprano es un algoritmo de aproximación 2 utilizando el argumento de carga, se debe demostrar que h es una función de dos a uno que mapea intervalos en OPT(I) a aquellos en EFT(I) . Supongamos que J es un intervalo arbitrario en OPT(I) .

Demuestre que h es una función que mapea OPT(I) a EFT(I) .

Primero, observe que existe algún intervalo en EFT(I) con la misma clase de trabajo que J , o no existe.

Caso 1. Supongamos que algún intervalo en EFT(I) tiene la misma clase de trabajo que J.

Si existe un intervalo en EFT(I) con la misma clase que J , entonces J se asignará a ese intervalo. Dado que los intervalos en EFT(I) son mutuamente compatibles, cada intervalo en EFT(I) debe tener una clase de trabajo diferente. Por lo tanto, dicho intervalo es único.

Caso 2. Supongamos que no hay intervalos en EFT(I) con la misma clase de trabajo que J.

Si no existen intervalos en EFT(I) de la misma clase que J , entonces h asigna a J el intervalo con el tiempo de finalización más temprano entre todos los intervalos en EFT(I) que intersecan a J. La demostración de la existencia y unicidad de dicho intervalo se presenta en el ejemplo anterior.

Demuestra que h es dos a uno.

Supongamos, por contradicción, que h no es de dos a uno. Entonces hay tres intervalos distintos en OPT(I) , J ₁ , J ₂ , y J ₃ , tales que h mapea cada uno de J ₁ , J ₂ , y J ₃ al mismo intervalo J' ∈ EFT(I) . Por el principio del palomar , al menos dos de los tres intervalos fueron mapeados a J' porque tienen la misma clase de trabajo que J ', o porque J ' es el intervalo con el tiempo de finalización más temprano entre todos los intervalos en EFT(I) que intersecan ambos intervalos. Sin pérdida de generalidad, supongamos que estos dos intervalos son J ₁ y J ₂ .

Caso 1. Supongamos que J ₁ y J ₂ se asignaron a J ' porque tienen la misma clase de trabajo que J '.

_{Entonces ,} cada J ', J1 y J2 tienen la misma clase de trabajo. Esto es una contradicción, ya que los intervalos en la solución óptima deben ser compatibles, pero J1 y _{J2 no lo son} .

Caso 2. Supongamos que J ' es el intervalo con el tiempo de finalización más temprano entre todos los intervalos en EFT(I) que intersecan tanto J ₁ como J ₂ .

La demostración de este caso es equivalente a la del ejemplo anterior que demostró la inyectividad. De la demostración anterior se deduce una contradicción.

Por lo tanto, h asigna no más de dos intervalos distintos en OPT(I) al mismo intervalo en EFT(I) , por lo que h tiene una relación de dos a uno. Según el argumento de tarificación, el algoritmo de tiempo de finalización más temprano es un algoritmo de aproximación doble para el problema de programación de intervalos de trabajo.