En informática , el problema del alquiler de esquís es un nombre que se le da a una clase de problemas en los que se puede elegir entre seguir pagando un costo repetido o pagar un costo único que elimina o reduce el costo repetido.
El problema
Muchos problemas en línea tienen un subproblema llamado problema de alquiler / compra. Necesitamos decidir si permanecer en el estado actual y pagar una cierta cantidad de costo por unidad de tiempo, o cambiar a otro estado y pagar un gran costo fijo sin más pagos. [1] El alquiler de esquís [2] [3] es un ejemplo en el que el alquiler / compra es todo el problema. Su versión básica es:
Una persona va a esquiar durante un número indeterminado de días. Alquilar esquís cuesta $ 1 por día y comprar esquís cuesta $ 10. Cada día, la persona debe decidir si continuar alquilando esquís un día más o comprar un par de esquís. Si la persona sabe de antemano cuántos días irá a esquiar, puede decidir su costo mínimo. Si va a esquiar por más de 10 días le saldrá más barato comprar esquís, pero si va a esquiar por menos de 10 días le saldrá más barato alquilar. ¿Qué debe hacer ella cuando no sabe de antemano cuántos días se esquiará? [ cita requerida ]
Formalmente, el problema se puede configurar de la siguiente manera. Hay un número de días d (desconocido) que la persona esquiará. El objetivo es encontrar un algoritmo que minimice la relación entre lo que paga la persona que usa el algoritmo (que no conoce d ) y lo que la persona pagaría de manera óptima si supiera d de antemano. El problema generalmente se analiza en el peor de los casos, donde el algoritmo es fijo y luego observamos el rendimiento del algoritmo en el peor de los casos sobre todos los posibles d . En particular, no se hacen suposiciones con respecto a la distribución de d (y es fácil ver que, con conocimiento de la distribución de d , se preferiría un análisis diferente, así como diferentes soluciones). [ cita requerida ]
El algoritmo de equilibrio
El algoritmo de equilibrio indica que uno debe alquilar durante 9 días y comprar esquís en la mañana del día 10 si todavía está listo para esquiar. [4] Si uno tiene que dejar de esquiar durante los primeros 9 días, cuesta lo mismo que pagaría si supiera el número de días que iría a esquiar. Si uno tiene que dejar de esquiar después del día 10, el costo es de $ 19, que es un 90% más de lo que pagaría si hubiera sabido con anticipación el número de días que iría a esquiar. Este es el peor de los casos para el algoritmo de equilibrio.
Se sabe que el algoritmo de equilibrio es el mejor algoritmo determinista para este problema.
Rompiendo incluso
Una persona puede lanzar una moneda. Si sale cara, compra esquís el día ocho; de lo contrario, compra esquís el día 10. Esta es una instancia de un algoritmo aleatorio . El costo esperado es como máximo un 80% más de lo que pagaría la persona si hubiera sabido el número de días que iría a esquiar, independientemente de cuántos días esquíe. En particular, si la persona esquía durante 10 días, su costo esperado es 1/2 [7 +10] + 1/2 [9 + 10] = 18 dólares, solo un 80% de exceso en lugar del 90%.
Un algoritmo aleatorizado puede entenderse como una composición de diferentes algoritmos, cada uno de los cuales ocurre con una probabilidad determinada. Definimos la relación competitiva esperada en una instancia i dada como:
, dónde es la relación competitiva, por ejemplo, i, dado .
En consecuencia, la razón competitiva de un algoritmo aleatorio viene dada por el peor valor de sobre todas las instancias dadas. En el caso del alquiler de esquís lanzando monedas, observamos que el algoritmo aleatorio tiene 2 ramas posibles: si la moneda sale cara, compramos el día 8, de lo contrario compramos el día 10. Podemos llamar a las sucursales y , respectivamente. , por .
,
, y
, por .
Por lo tanto, la relación competitiva del algoritmo de lanzamiento aleatorio de monedas de alquiler de esquís es 1.8.
El mejor algoritmo aleatorizado contra un adversario ajeno es elegir algún día i al azar de acuerdo con la siguiente distribución p, alquilar por i-1 días y comprar esquís en la mañana del día i si uno todavía está listo para esquiar. Karlin y col. [2] presentó por primera vez este algoritmo con distribución donde comprar esquís cuesta $y el alquiler cuesta $ 1. Su costo esperado es como máximo e / (e-1)1,58 veces lo que se pagaría si se supiera el número de días que se iría a esquiar. Ningún algoritmo aleatorio puede hacerlo mejor.
Aplicaciones
- Almacenamiento en caché de Snoopy : [2] varias cachés comparten el mismo espacio de memoria que está dividido en bloques. Cuando un caché escribe en un bloque, los cachés que comparten el bloque gastan 1 ciclo de bus para actualizarse. Estos cachés pueden invalidar el bloque para evitar el costo de actualización. Pero existe una penalización de p ciclos de bus por invalidar un bloque de un caché que poco después necesita acceder a él. Podemos dividir las secuencias de solicitud de escritura para varios cachés en secuencias de solicitud para dos cachés. Una caché realiza una secuencia de operaciones de escritura en el bloque. La otra caché debe decidir si actualizarse pagando 1 ciclo de bus por operación o invalidar el bloque pagando p ciclos de bus por la futura solicitud de lectura de sí mismo. El problema de dos cachés, un bloque de caché snoopy es solo el problema del alquiler de esquís.
- Reconocimiento de TCP : [5] Un flujo de paquetes llega a un destino y el protocolo TCP requiere que se reconozcan al llegar. Sin embargo, podemos usar un solo paquete de reconocimiento para reconocer simultáneamente múltiples paquetes pendientes, reduciendo así la sobrecarga de los reconocimientos. Por otro lado, retrasar demasiado los reconocimientos puede interferir con los mecanismos de control de congestión del TCP y, por lo tanto, no deberíamos permitir que la latencia entre la hora de llegada de un paquete y la hora en que se envía el reconocimiento aumente demasiado. Karlin y col. [6] describió una familia de entradas de un parámetro, llamadas entradas de base, y mostró que cuando se restringe a estas entradas de base, el problema de reconocimiento de TCP se comporta igual que el problema de alquiler de esquís.
- Programación del tiempo total de finalización : [1] Deseamos programar trabajos con tiempos de procesamiento fijos en m máquinas idénticas. El tiempo de procesamiento del trabajo j es p j . El planificador conoce cada trabajo en su momento de publicación r j . El objetivo es minimizar la suma de los tiempos de finalización de todos los trabajos. Un problema simplificado es una sola máquina con la siguiente entrada: en el tiempo 0, llega un trabajo con el tiempo de procesamiento 1; k trabajos con tiempo de procesamiento 0 llegan en un momento desconocido. Necesitamos elegir una hora de inicio para el primer trabajo. Esperar tiene un costo de 1 por unidad de tiempo, sin embargo, comenzar el primer trabajo antes de los k trabajos posteriores puede incurrir en un costo adicional de k en el peor de los casos. Este problema simplificado puede verse como una versión continua del problema del alquiler de esquís.
- Refactorizar versus trabajar con un diseño deficiente : en el desarrollo de software, los ingenieros deben elegir entre la fricción y el riesgo de errores de trabajar con un diseño demasiado complejo y reducir la complejidad del diseño antes de realizar un cambio. El costo adicional de cada cambio con el diseño antiguo es el costo de "alquiler", el costo de refactorización es el costo de "compra". "¿Cuántas veces se trabaja con un diseño deficiente antes de limpiarlo?" es un problema de alquiler de esquís.
Ver también
Referencias
- ↑ a b Steven S. Seiden. Un juego de adivinanzas y algoritmos en línea aleatorios. Simposio anual de ACM sobre teoría de la computación, 2000. http://portal.acm.org/citation.cfm?id=335385
- ^ a b c A. R. Karlin , MS Manasse, LA McGeoch y S. Owicki. Algoritmos competitivos aleatorizados para problemas no uniformes. En Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 22-24 de enero de 1990, págs. 301-309. También en Algorithmica, 11 (6): 542-571, 1994. http://courses.csail.mit.edu/6.895/fall03/handouts/papers/karlin.pdf
- ^ Claire Mathieu . Universidad de Brown. Nota de la conferencia: http://www.cs.brown.edu/~claire/Talks/skirental.pdf
- ^ AR Karlin , M. Manasse, L. Rudolph y D. Sleator. Almacenamiento en caché competitivo de snoopy. Algoritmica, 3 (1): 79-119, 1988
- ^ DR Dooly, SA Goldman y SD Scott. Retardo de reconocimiento dinámico de TCP: teoría y práctica. En Actas del Trigésimo Simposio Anual de ACM sobre Teoría de la Computación (STOC), Dallas, TX, págs. 389-398, 1998.
- ^ Anna R. Karlin y Claire Kenyon y Dana Randall. Reconocimiento de TCP dinámico y otras historias sobre e / (e-1). Trigésimo tercer simposio anual de ACM sobre teoría de la computación (STOC), 2001. Algorithmica. http://www.cs.brown.edu/people/claire/Publis/ACKpaper.ps