@prefix owl: . @prefix dbr: . @prefix dbpedia-es: . dbr:K-server_problem owl:sameAs dbpedia-es:Problema_k-server . @prefix foaf: . @prefix wikipedia-es: . wikipedia-es:Problema_k-server foaf:primaryTopic dbpedia-es:Problema_k-server . @prefix rdfs: . dbpedia-es:Problema_k-server rdfs:label "Problema k-server"@es ; rdfs:comment "El problema k-server es un problema de teor\u00EDa de la ciencia de la computaci\u00F3n en la categor\u00EDa de algoritmos en l\u00EDnea, uno de dos problemas abstractos en espacios m\u00E9tricos que es central a la teor\u00EDa de (el otro es ). En este problema, un algoritmo en l\u00EDnea tiene que controlar el movimiento de un conjunto de k servidores, representados como puntos en un espacio m\u00E9trico, y manejar peticiones que est\u00E1n tambi\u00E9n en la forma de puntos en el espacio. Cuando cada petici\u00F3n llega, el algoritmo tiene que determinar qu\u00E9 servidor mover al punto pedido. El objetivo del algoritmo es mantener la distancia total de todos los movimientos de los servidores peque\u00F1a, relativa a la distancia total que los servidores se podr\u00EDan haber movido por un adversario \u00F3ptimo quien sabe por adelantado la secuencia entera d"@es ; owl:sameAs dbpedia-es:Problema_k-server . @prefix dct: . dbpedia-es:Problema_k-server dct:subject ; foaf:isPrimaryTopicOf wikipedia-es:Problema_k-server . @prefix dbo: . dbpedia-es:Problema_k-server dbo:wikiPageID 7075704 ; dbo:wikiPageRevisionID 124742999 ; dbo:wikiPageExternalLink . @prefix xsd: . dbpedia-es:Problema_k-server dbo:wikiPageLength "8185"^^xsd:nonNegativeInteger ; "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 ; 1995 , 1991 , 1985 . @prefix prop-es: . dbpedia-es:Problema_k-server prop-es:volumen 42 , 28 , 20 ; 971 , 144 , 202 ; 1 , 2 , 5 ; prop-es:doi 101137 , 101145 ; prop-es:title "Competitive k-server algorithms"@es ; prop-es:date 1990 ; prop-es:autor "Koutsoupias, Elias; Papadimitriou, Christos H."@es , dbpedia-es:Robert_Tarjan , dbpedia-es:Marek_Chrobak , , dbpedia-es:Daniel_Sleator ; prop-es:booktitle "Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science"@es . @prefix prov: . dbpedia-es:Problema_k-server prov:wasDerivedFrom ; dbo:abstract "El problema k-server es un problema de teor\u00EDa de la ciencia de la computaci\u00F3n en la categor\u00EDa de algoritmos en l\u00EDnea, uno de dos problemas abstractos en espacios m\u00E9tricos que es central a la teor\u00EDa de (el otro es ). En este problema, un algoritmo en l\u00EDnea tiene que controlar el movimiento de un conjunto de k servidores, representados como puntos en un espacio m\u00E9trico, y manejar peticiones que est\u00E1n tambi\u00E9n en la forma de puntos en el espacio. Cuando cada petici\u00F3n llega, el algoritmo tiene que determinar qu\u00E9 servidor mover al punto pedido. El objetivo del algoritmo es mantener la distancia total de todos los movimientos de los servidores peque\u00F1a, relativa a la distancia total que los servidores se podr\u00EDan haber movido por un adversario \u00F3ptimo quien sabe por adelantado la secuencia entera de peticiones. El problema fue presentado por , Lyle Un. McGeoch Y Daniel Sleator (1990). La cuesti\u00F3n abierta m\u00E1s prominente respecto del problema k-server es la llamada cojetura k-server, tambi\u00E9n presentado por Manasse, McGeoch y Sleator. Esta conjetura declara que hay un algoritmo para solucionar el problema k-server en un espacio m\u00E9trico arbitrario y para cualquier n\u00FAmero k de servidores que tiene proporci\u00F3n competitiva al menos k. Manasse, McGeoch y Sleator fueron capaces de probar su conjetura cuando k = 2, y para valores m\u00E1s generales de k cuando el espacio m\u00E9trico est\u00E1 restringido para tener exactamente k+1 puntos. Chrobak y Larmore (1991) probaron la conjetura para la m\u00E9trica (norma) de \u00E1rbol. El caso especial de m\u00E9trica (norma) en que todas distancias son iguales es llamado el problema de paginaci\u00F3n porque modela el problema de algoritmos de sustituci\u00F3n de p\u00E1gina en cach\u00E9s de memoria, y era tambi\u00E9n ya sabido tener un algoritmo k-competitivo (Sleator y Tarjan 1985). Manasse, McGeoch y Sleator (1990) probaron que existe un algoritmo con proporci\u00F3n competitiva finita para cualquier constante k y cualquier espacio m\u00E9trico, y finalmente Koutsoupias y Papadimitriou (1995) probaron que el algoritmo Work Function (WFA) tiene proporci\u00F3n competitiva 2k - 1. Aun as\u00ED, a pesar de los esfuerzos de muchos otros investigadores, reduciendo la proporci\u00F3n competitiva a k o proporcionando una cota inferior mejorada, se mantiene aun abierto. El escenario cre\u00EDdo m\u00E1s com\u00FAn es que el WFA es k-competitivo. Respecto a esto, en el a\u00F1o 2000 Bartal y Koutsoupias mostraron que esto es cierto para algunos casos especiales (si el espacio m\u00E9trico es una l\u00EDnea, una estrella ponderada o cualquier m\u00E9trica (norma) de k+2 puntos). En 2011, se encontr\u00F3 un algoritmo aleatorio de costo \u00D5(log2k log3n).\u200B"@es ; "SIAM Journal on Computing"@es , "Communications of the ACM"@es , "Journal of the ACM"@es ; prop-es:author "Fiat, A.; Rabani, Y.; Ravid, Y."@es ; prop-es:pages 454 .