| Property |
Value |
| dbo:abstract
|
- El problema k-server es un problema de teoría de la ciencia de la computación en la categoría de algoritmos en línea, uno de dos problemas abstractos en espacios métricos que es central a la teoría de (el otro es ). En este problema, un algoritmo en línea tiene que controlar el movimiento de un conjunto de k servidores, representados como puntos en un espacio métrico, y manejar peticiones que están también en la forma de puntos en el espacio. Cuando cada petición llega, el algoritmo tiene que determinar qué servidor mover al punto pedido. El objetivo del algoritmo es mantener la distancia total de todos los movimientos de los servidores pequeña, relativa a la distancia total que los servidores se podrían haber movido por un adversario óptimo quien sabe por adelantado la secuencia entera de peticiones. El problema fue presentado por , Lyle Un. McGeoch Y Daniel Sleator (1990). La cuestión abierta más prominente respecto del problema k-server es la llamada cojetura k-server, también presentado por Manasse, McGeoch y Sleator. Esta conjetura declara que hay un algoritmo para solucionar el problema k-server en un espacio métrico arbitrario y para cualquier número k de servidores que tiene proporción competitiva al menos k. Manasse, McGeoch y Sleator fueron capaces de probar su conjetura cuando k = 2, y para valores más generales de k cuando el espacio métrico está restringido para tener exactamente k+1 puntos. Chrobak y Larmore (1991) probaron la conjetura para la métrica (norma) de árbol. El caso especial de métrica (norma) en que todas distancias son iguales es llamado el problema de paginación porque modela el problema de algoritmos de sustitución de página en cachés de memoria, y era también ya sabido tener un algoritmo k-competitivo (Sleator y Tarjan 1985). Manasse, McGeoch y Sleator (1990) probaron que existe un algoritmo con proporción competitiva finita para cualquier constante k y cualquier espacio métrico, y finalmente Koutsoupias y Papadimitriou (1995) probaron que el algoritmo Work Function (WFA) tiene proporción competitiva 2k - 1. Aun así, a pesar de los esfuerzos de muchos otros investigadores, reduciendo la proporción competitiva a k o proporcionando una cota inferior mejorada, se mantiene aun abierto. El escenario creído más común es que el WFA es k-competitivo. Respecto a esto, en el año 2000 Bartal y Koutsoupias mostraron que esto es cierto para algunos casos especiales (si el espacio métrico es una línea, una estrella ponderada o cualquier métrica (norma) de k+2 puntos). En 2011, se encontró un algoritmo aleatorio de costo Õ(log2k log3n). (es)
- El problema k-server es un problema de teoría de la ciencia de la computación en la categoría de algoritmos en línea, uno de dos problemas abstractos en espacios métricos que es central a la teoría de (el otro es ). En este problema, un algoritmo en línea tiene que controlar el movimiento de un conjunto de k servidores, representados como puntos en un espacio métrico, y manejar peticiones que están también en la forma de puntos en el espacio. Cuando cada petición llega, el algoritmo tiene que determinar qué servidor mover al punto pedido. El objetivo del algoritmo es mantener la distancia total de todos los movimientos de los servidores pequeña, relativa a la distancia total que los servidores se podrían haber movido por un adversario óptimo quien sabe por adelantado la secuencia entera de peticiones. El problema fue presentado por , Lyle Un. McGeoch Y Daniel Sleator (1990). La cuestión abierta más prominente respecto del problema k-server es la llamada cojetura k-server, también presentado por Manasse, McGeoch y Sleator. Esta conjetura declara que hay un algoritmo para solucionar el problema k-server en un espacio métrico arbitrario y para cualquier número k de servidores que tiene proporción competitiva al menos k. Manasse, McGeoch y Sleator fueron capaces de probar su conjetura cuando k = 2, y para valores más generales de k cuando el espacio métrico está restringido para tener exactamente k+1 puntos. Chrobak y Larmore (1991) probaron la conjetura para la métrica (norma) de árbol. El caso especial de métrica (norma) en que todas distancias son iguales es llamado el problema de paginación porque modela el problema de algoritmos de sustitución de página en cachés de memoria, y era también ya sabido tener un algoritmo k-competitivo (Sleator y Tarjan 1985). Manasse, McGeoch y Sleator (1990) probaron que existe un algoritmo con proporción competitiva finita para cualquier constante k y cualquier espacio métrico, y finalmente Koutsoupias y Papadimitriou (1995) probaron que el algoritmo Work Function (WFA) tiene proporción competitiva 2k - 1. Aun así, a pesar de los esfuerzos de muchos otros investigadores, reduciendo la proporción competitiva a k o proporcionando una cota inferior mejorada, se mantiene aun abierto. El escenario creído más común es que el WFA es k-competitivo. Respecto a esto, en el año 2000 Bartal y Koutsoupias mostraron que esto es cierto para algunos casos especiales (si el espacio métrico es una línea, una estrella ponderada o cualquier métrica (norma) de k+2 puntos). En 2011, se encontró un algoritmo aleatorio de costo Õ(log2k log3n). (es)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:author
|
- Fiat, A.; Rabani, Y.; Ravid, Y. (es)
- Fiat, A.; Rabani, Y.; Ravid, Y. (es)
|
| prop-es:autor
| |
| prop-es:año
|
- 1985 (xsd:integer)
- 1991 (xsd:integer)
- 1995 (xsd:integer)
|
| prop-es:booktitle
|
- Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (es)
- Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (es)
|
| prop-es:date
| |
| prop-es:doi
|
- 101137 (xsd:integer)
- 101145 (xsd:integer)
|
| prop-es:número
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 5 (xsd:integer)
|
| prop-es:pages
| |
| prop-es:publicación
|
- Journal of the ACM (es)
- SIAM Journal on Computing (es)
- Communications of the ACM (es)
- Journal of the ACM (es)
- SIAM Journal on Computing (es)
- Communications of the ACM (es)
|
| prop-es:páginas
|
- 144 (xsd:integer)
- 202 (xsd:integer)
- 971 (xsd:integer)
|
| prop-es:title
|
- Competitive k-server algorithms (es)
- Competitive k-server algorithms (es)
|
| prop-es:título
|
- On the k-server conjecture (es)
- Amortized efficiency of list update and paging rules (es)
- An optimal on-line algorithm for K-servers on trees (es)
- On the k-server conjecture (es)
- Amortized efficiency of list update and paging rules (es)
- An optimal on-line algorithm for K-servers on trees (es)
|
| prop-es:volumen
|
- 20 (xsd:integer)
- 28 (xsd:integer)
- 42 (xsd:integer)
|
| dct:subject
| |
| rdfs:comment
|
- El problema k-server es un problema de teoría de la ciencia de la computación en la categoría de algoritmos en línea, uno de dos problemas abstractos en espacios métricos que es central a la teoría de (el otro es ). En este problema, un algoritmo en línea tiene que controlar el movimiento de un conjunto de k servidores, representados como puntos en un espacio métrico, y manejar peticiones que están también en la forma de puntos en el espacio. Cuando cada petición llega, el algoritmo tiene que determinar qué servidor mover al punto pedido. El objetivo del algoritmo es mantener la distancia total de todos los movimientos de los servidores pequeña, relativa a la distancia total que los servidores se podrían haber movido por un adversario óptimo quien sabe por adelantado la secuencia entera d (es)
- El problema k-server es un problema de teoría de la ciencia de la computación en la categoría de algoritmos en línea, uno de dos problemas abstractos en espacios métricos que es central a la teoría de (el otro es ). En este problema, un algoritmo en línea tiene que controlar el movimiento de un conjunto de k servidores, representados como puntos en un espacio métrico, y manejar peticiones que están también en la forma de puntos en el espacio. Cuando cada petición llega, el algoritmo tiene que determinar qué servidor mover al punto pedido. El objetivo del algoritmo es mantener la distancia total de todos los movimientos de los servidores pequeña, relativa a la distancia total que los servidores se podrían haber movido por un adversario óptimo quien sabe por adelantado la secuencia entera d (es)
|
| rdfs:label
|
- Problema k-server (es)
- Problema k-server (es)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
