| 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)
- The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems). In this problem, an online algorithm must control the movement of a set of k servers, represented as points in a metric space, and handle requests that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests. (en)
- Задача о k официантах (или исполнителях) — это задача теоретической информатики в категории , одна из двух абстрактных задач в метрических пространствах, являющаяся центральной в теории (другая — ). В этой задаче онлайн-алгоритм должен контролировать передвижение множества k исполнителей, представленных точками в метрическом пространстве, и обрабатывать запросы, которые также представлены точками в пространстве. Когда приходит запрос, алгоритм должен определить, какого исполнителя послать к запрашивающей точке. Целью алгоритма является получение минимального отношения общего расстояния, проходимого исполнителями, к общему расстоянию, которое исполнители прошли бы, если бы двигались по оптимальным маршрутам при известной последовательности запросов. Это отношение называется уровнем эффекти (ru)
|
| has abstract
| - The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems). In this problem, an online algorithm must control the movement of a set of k servers, represented as points in a metric space, and handle requests that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests. The problem was first posed by , Lyle A. McGeoch and Daniel Sleator (1990). The most prominent open question concerning the k-server problem is the so-called k-server conjecture, also posed by Manasse et al. This conjecture states that there is an algorithm for solving the k-server problem in an arbitrary metric space and for any number k of servers that has competitive ratio exactly k. Manasse et al. were able to prove their conjecture when k = 2, and for more general values of k when the metric space is restricted to have exactly k+1 points. Chrobak and Larmore (1991) proved the conjecture for tree metrics. The special case of metrics in which all distances are equal is called the paging problem because it models the problem of page replacement algorithms in memory caches, and was also already known to have a k-competitive algorithm (Sleator and Tarjan 1985). Fiat et al. (1990) first proved that there exists an algorithm with finite competitive ratio for any constant k and any metric space, and finally Koutsoupias and Papadimitriou (1995) proved that Work Function Algorithm (WFA) has competitive ratio 2k - 1. However, despite the efforts of many other researchers, reducing the competitive ratio to k or providing an improved lower bound remains open as of 2014. The most common believed scenario is that the Work Function Algorithm is k-competitive. To this direction, in 2000 Bartal and Koutsoupias showed that this is true for some special cases (if the metric space is a line, a weighted star or any metric of k+2 points). In 2011, a randomized algorithm with competitive bound Õ(log2k log3n) was found. In 2017, a randomized algorithm with competitive bound O(log6 k) was announced, but was later retracted. (en)
- 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)
- Задача о k официантах (или исполнителях) — это задача теоретической информатики в категории , одна из двух абстрактных задач в метрических пространствах, являющаяся центральной в теории (другая — ). В этой задаче онлайн-алгоритм должен контролировать передвижение множества k исполнителей, представленных точками в метрическом пространстве, и обрабатывать запросы, которые также представлены точками в пространстве. Когда приходит запрос, алгоритм должен определить, какого исполнителя послать к запрашивающей точке. Целью алгоритма является получение минимального отношения общего расстояния, проходимого исполнителями, к общему расстоянию, которое исполнители прошли бы, если бы двигались по оптимальным маршрутам при известной последовательности запросов. Это отношение называется уровнем эффективности алгоритма (чем меньше отношение, тем алгоритм эффективнее). (ru)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)