Análisis competitivo aleatorio para dos problemas de servidor
Autores: Bein, Wolfgang; Iwama, Kazuo; Kawahara, Jun
Idioma: Inglés
Editor: MDPI
Año: 2008
Acceso abierto
Artículo científico
2008
Análisis competitivo aleatorio para dos problemas de servidor
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Aleatorio
En línea
2-servidor
Ratio competitivo
Espacio métrico
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 35
Citaciones: Sin citaciones
Demostramos que existe un algoritmo en línea aleatorio para el problema de 2 servidores y 3 puntos cuya relación competitiva esperada es como máximo 1.5897. Esta es la primera cota superior no trivial para algoritmos de -servidores aleatorios en un espacio métrico general cuya relación competitiva está muy por debajo de la cota inferior determinista correspondiente (= 2 en el caso de 2 servidores).
Descripción
Demostramos que existe un algoritmo en línea aleatorio para el problema de 2 servidores y 3 puntos cuya relación competitiva esperada es como máximo 1.5897. Esta es la primera cota superior no trivial para algoritmos de -servidores aleatorios en un espacio métrico general cuya relación competitiva está muy por debajo de la cota inferior determinista correspondiente (= 2 en el caso de 2 servidores).