Problema k-server

El problema k-server és un problema de teoria de la ciència de la computació en la categoria d'algoritmes en llínea, un de dos problemes abstractes en espais mètrics que és central a la teoria d'anàlisis competitiu (l'atre és sistemes de tasca mètrica). En este problema, un algoritme en llínea té que controlar el moviment d'un conjunt de k servidors, representats com a punts en un espai mètric, i manejar peticions que estan també en la forma de punts en l'espai. Quan cada petició aplega, l'algoritme té que determinar qué servidor moure al punt demanat. L'objectiu de l'algoritme és mantindre la distància total de tots els moviments dels servidors menuda, relativa a la distància total que els servidors es podrien haver mogut per un adversari òptim qui sap per avant la seqüència sancera de peticions.

El problema va ser presentat per Mark Manasse, Lyle Un. McGeoch I Daniel Sleator (1990). La qüestió oberta més prominent respecte del problema k-server és la cridada cojetura k-server, també presentat per Manasse, McGeoch i Sleator. Esta conjectura declara que hi ha un algoritme per a solucionar el problema k-server en un espai mètric arbitrari i per a qualsevol número k de servidors que té proporció competitiva a lo manco k. Manasse, McGeoch i Sleator varen ser capaços de provar la seua conjectura quan k = 2, i per a valors més generals de k quan l'espai mètric està restringit per a tindre exactament k+1 punts. Chrobak i Larmore (1991) varen provar la conjectura per a la mètrica (norma) d'arbre. El cas especial de mètrica (norma) en que totes distàncies són iguals és cridat el problema de paginació perque modela el problema d'algoritmes de substitució de pàgina en cachés de memòria, i era també ya sabut tindre un algoritme k-competitiu (Sleator i Tarjan 1985). Manasse, McGeoch i Sleator (1990) varen provar que existix un algoritme en proporció competitiva finita per a qualsevol constant k i qualsevol espai mètric, i finalment Koutsoupias i Papadimitriou (1995) varen provar que l'algoritme Work Function (WFA) té proporció competitiva 2k - 1. Aixina i tot, a pesar dels esforços de molts atres investigadors, reduint la proporció competitiva a k o proporcionant una cota inferior millorada, es manté encara obert. L'escenari cregut més comú és que el WFA és k-competitiu. Respecte a açò, en l'any 2000 Bartal i Koutsoupias varen mostrar que açò és cert per a alguns casos especials (si l'espai mètric és una llínea, una estrela ponderada o qualsevol mètrica (norma) de k+2 punts).

En 2011, es va trobar un algoritme aleatori de cost Õ(log²k log³n).

Eixemple

Per a fer el problema més concret, imagina enviar tècnics de soport del client a clients quan tenen problema en el seu equipament. En el nostre problema d'eixemple hi ha dos tècnics, Mary i Noah, servint tres clients, en Sant Francisco, Califòrnia; Washington D. C.; i Baltimore, Maryland. Com en el problema k-server, els servidors són els tècnics, per lo que k = 2 i açò és un problema 2-server. Washington i Baltimore estan a 35 milles (56 km) de distància, mentres Sant Francisco està a 3,000 milles (4,800 km) d'abdós, i inicialment Mary i Noah estan abdós en Sant Francisco.

Considerar un algoritme per a assignar servidors a peticions que sempre assigna el servidor més propenc a la petició, i supondre que cada dia en el matí el client en Washington necessita assistència mentres cada dia en la vesprada el client en Baltimore necessita assistència, i que el client en Sant Francisco mai necessita assistència. Llavors, el nostre algoritme assignarà un dels servidors (per eixemple Mary) a l'àrea de Washington, despuix de la qual sempre serà el servidor més propenc i sempre serà assignat a totes peticions de client. Aixina, tots els dies el nostre algoritme incorre el cost de viajar entre Washington i Baltimore d'anada i regrés, 70 milles (110 km). Despuix d'un any d'este patró de petició, l'algoritme haurà incorregut 20,500 milles (33,000 km) de viage: 3000 per a enviar Mary a la Costa Este, i 17,500 per als viages entre Washington i Baltimore. Per un atre costat, un adversari òptim que sap el programa de petició futur podria haver enviat abdós Mary i Noah a Washington i Baltimore respectivament, pagant 6,000 milles (9,700 km) de viajar una volta pero llavors evitant qualsevol costs de viage futurs. La proporció competitiva del nostre algoritme en esta entrada és 20,500/6000 o aproximadament 3.4, i ajustant els paràmetros d'este eixemple la proporció competitiva d'este algoritme pot ser feta arbitrariamente gran.

Per això veem que sempre assignant el servidor més propenc pot distar molt de la solució optimal. Per un atre costat, sembla mec per a un algoritme que no sap peticions futures enviar un dels seus tècnics fòra de Sant Francisco, quan la petició pròxima podria ser en aquella ciutat i tindrien que enviar algú de tornada immediatament. Per lo tant, sembla que és difícil o impossible per a un algoritme k-server actuar ben relatiu al seu adversari. Aixina i tot, per al problema 2-server existix un algoritme que sempre té una distància de viage total de com a màxim dos voltes la distància de l'adversari. La conjectura k-server declara que les solucions similars existixen per a problemes en qualsevol número gran de tècnics.

Referències

• Chrobak, Marek; Larmore, Lawrence L.(1991).SIAM Journal on Computing.20(1)

144–148.doi:10.1137/0220008.

• Koutsoupias, Elias; Papadimitriou, Christos H.(1995).Journal of the ACM.42(5)

971–983.doi:10.1145/210118.210128.

• Manasse, Mark; McGeoch, Lyle A.; Sleator, Daniel D. (1990). "Competitive algorithms for server problems". Journal of Algorithms 11 (2): 208–230. doi:10.1016/0196-6774(90)90003-W. 

• Sleator, Daniel D.; Tarjan, Robert E.(1985).Communications of the ACM.28(2)

202–208.doi:10.1145/2786.2793.