A k-szerver probl´ ema Imreh Csan´ad SZTE, Informatikai Tansz´ekcsoport ´ ad t´er 2. 6720, Szeged, Arp´ Email:
[email protected] Bevezet´ es A gyakorlatban gyakran fordulnak el˝o olyan optimaliz´al´asi feladatok, ahol az inputot csak r´eszenk´ent ismerj¨ uk meg, ´es a d¨ont´eseinket a m´ar megkapott inform´aci´ok alapj´an a tov´abbi adatok ismerete n´elk¨ ul kell meghoznunk. Ilyen feladatok eset´en online probl´em´ ar´ ol besz´el¨ unk. Az online algoritmusok elm´elet´enek igen sok alkalmaz´asa van a sz´am´ıt´astudom´any, a k¨ozgazdas´agtan, ´es az oper´aci´okutat´as k¨ ul¨onb¨oz˝o ter¨ uletein. Az online algoritmusok hat´ekonys´ag´anak vizsg´alat´ara haszn´alt legelterjedtebb m´odszer a kompetit´ıv anal´ızis. Az online algoritmus ´altal kapott megold´as k¨olts´eg´et hasonl´ıtjuk ¨ossze az optim´alis offline (az offline esetben az algoritmus m´ar kezdetben ismeri az eg´esz inputot) c´elf¨ uggv´eny´ert´ekkel. Az al´abbiakban pontosabban defini´aljuk ezen m´odszer alapvet˝o fogalmait. Egy online algoritmust C-kompetit´ıvnek nevez¨ unk, ha minden inputra az algoritmus ´altal kapott megold´as k¨olts´ege nem nagyobb, mint C-szer az optim´alis offline k¨olts´eg. Egy algoritmus kompetit´ıv h´ anyadosa a legkisebb olyan C sz´am, amelyre az algoritmus C-kompetit´ıv. Egy probl´ema kompetit´ıv h´ anyadosa a legkisebb kompetit´ıv h´anyados, amelyet online algoritmus el tud ´erni. Az egyik legismertebb online probl´ema a k-szerver probl´ema. A feladatban adott egy metrikus t´er, ´es van k szerver¨ unk, amelyek a t´erben mozoghatnak. A probl´ema sor´an a t´er pontjaib´ol ´all´o k´er´esek egy list´aj´at kell kiel´eg´ıteni az´altal, hogy a megfelel˝o k´er´esek hely´ere odak¨ uld¨ unk egy-egy szervert. A probl´ema online, ami azt jelenti, hogy az ig´enyeket egyenk´ent kapjuk meg, ´es az egyes ig´enyeket a tov´abbi k´er´esek ismerete n´elk¨ ul kell kiel´eg´ıten¨ unk. A c´elunk a szerverek ´altal megtett ¨osszt´avols´ag minimaliz´al´asa. Ezen modellnek ´es speci´alis eseteinek sz´amos alkalmaz´asa van. Ebben a dolgozatban r¨oviden ¨osszefoglaljuk a k-szerver probl´em´ara vonatkoz´o legismertebb, ma m´ar klasszikusnak sz´am´ıt´o eredm´enyeket, (egy r´eszletesebb ´attekint´es megtal´alhat´o az [5] surveyben), majd r¨oviden kit´er¨ unk
1
n´eh´any mostan´aban felvetett ´altal´anos´ıt´asra ´es szorosan kapcsol´od´o egy´eb probl´em´ara. Alapvet˝ o eredm´ enyek a k-szerver probl´ em´ ara Az els˝o fontos eredm´enyeket a k szerver probl´em´ara a [13] cikkben igazolt´ak. Megmutatt´ak, hogy nincs olyan legal´abb k + 1 pontb´ol ´all´o metrikus t´er, ahol megadhat´o olyan online algoritmus, amelynek kisebb a kompetit´ıv h´anyadosa, mint k. A probl´ema nagy ´erdekl˝od´est keltett, az elk¨ovetkez˝o n´eh´any ´evben sz´amos eredm´eny sz¨ uletett. Az ´altal´anos esetre els˝ok´ent konstans kompetit´ıv (O(2k )kompetit´ıv) algoritmust a [8] cikkben publik´altak. Ezt k¨ovet˝oen hosszan nem siker¨ ult l´enyegesen cs¨okkenteni a fels˝o ´es az als´o korl´at k¨oz¨otti r´est. Az ´att¨or´est a [11] dolgozatban k¨oz¨olt eredm´eny hozta. A dolgozatban siker¨ ult a [4] cikkben javasolt munkaf¨ uggv´enyen alapul´o algoritmust analiz´alni, ´es igazolt´ak, hogy az algoritmus 2k − 1-kompetit´ıv. Nem siker¨ ult meghat´arozni az algoritmus kompetit´ıv h´anyados´at, b´ar ´altal´anosan sejtett, hogy az algoritmus val´oj´aban k-kompetit´ıv. Ezen kompetit´ıv h´anyados pontos meghat´aroz´asa, illetve egy k-kompetit´ıv algoritmus kifejleszt´ese az´ota is az online algoritmusok elm´elet´enek legismertebb ´es sokak ´altal legfontosabbnak tartott ny´ılt probl´em´aja. A probl´ema speci´alis eseteit sz´amos dolgozatban vizsg´alt´ak. A k = 2 esetre m´ar az eredeti [13] dolgozatban bemutattak egy 2-kompetit´ıv algoritmust, ´es k´es˝obb t¨obb egyszer˝ ubb illetve gyorsabb 2-kompetit´ıv algoritmust is kifejlesztettek. Szint´en igazol´ast nyert, hogy az a kiegyens´ ulyoz´o algoritmus, amely igyekszik a szerverek ´altal megtett t´avols´agot egyenletesen elosztani k-kompetit´ıv abban az esetben, ha a metrikus t´er pontjainak sz´ama k + 1. Szint´en sok cikk foglalkozik speci´alis metrikus terekkel. Amennyiben b´armely k´et pont t´avols´aga 1, akkor a lapoz´asi probl´em´ahoz jutunk, amely a sz´am´ıt´og´epek mem´oriakezel´es´et modellezi, ezt a probl´em´at sz´amos dolgozat tanulm´anyozza, egy ´attekint´es tal´alhat´o a [10] surveyben. Amennyiben a metrikus t´er egy egyenes vagy egy fa, akkor megadhat´o k-kompetit´ıv algoritmus (ld. [3]) A kezdeti alapvet˝o eredm´enyek ut´an t¨obb dolgozat foglalkozott egy´eb speci´alis esetekkel, ´es sz´amos eredm´eny sz¨ uletett a v´eletlen´ıtett online algoritmusokhoz kapcsol´od´oan. Tov´abb´a olyan algoritmusokat vizsg´altak, amelyeknek korl´atozott a mem´ori´ajuk. Itt ezekkel az eredm´enyekkel nem foglalkozunk, ink´abb az eredeti k-szerver probl´em´ahoz kapcsol´od´o modelleket mutatjuk be r¨oviden. 2
Egy´ eb kapcsol´ od´ o modellek S´ ulyozott szerverek: Az egyik legfontosabb ´altal´anos´ıt´asa a k-szerver probl´em´anak a s´ ulyozott k-szerver probl´ema. Ebben a probl´em´aban minden szervernek van egy s´ ulya (az i-edik szerver s´ ulya wi ), ´es amennyiben az i-edik szerver szolg´al ki egy a szerver poz´ıci´oj´at´ol d t´avols´agra es˝o k´er´est, akkor ennek a k¨olts´ege dwi . Ez a probl´ema igen neh´eznek bizonyult, csak kev´es hozz´a kapcsol´od´o eredm´eny ismert. Az uniform terek eset´et (b´armely k´et pont t´avols´aga 1) vizsg´alja ´altal´anos k-ra a [9] dolgozat, ahol k-ban dupl´an exponenci´alis kompetit´ıv h´anyadossal rendelkez˝o algoritmust fejlesztettek ki. A k = 2 esetet vizsg´alj´ak a [6] ´es [7] dolgozatok, [6] tetsz˝oleges sebess´egek eset´en vizsg´alja a probl´em´at, a [7] dolgozat f˝oleg azzal az esettel foglalkozik, amelyben a szerverek sebess´eg´enek h´anyadosa kicsi. Online utaz´ ou ¨ gyn¨ ok probl´ ema: Az online utaz´o u ¨gyn¨ok probl´em´aban (ld. [1]) egyetlen szerver¨ unk van, amellyel k´er´eseket kell kiel´eg´ıten¨ unk. A k¨ ul¨onbs´eg az, hogy a k´er´eseket nem az adott sorrendben kell kiel´eg´ıteni, hanem a k´er´eseknek van egy ´erkez´esi ideje, ´es a k´er´eseket b´armikor kiel´eg´ıthetj¨ uk az ´erkez´esi idej¨ uk ut´an. A szerver egys´eg sebess´eggel mozog, a probl´ema online, ami azt jelenti, hogy egy adott id˝opontban csak az addig be´erkezett k´er´eseket ismerj¨ uk ´es semmit nem tudunk a t¨obbi k´er´esr˝ol. A c´el az, hogy min´el hamarabb fejezz¨ uk be a k´er´esek kiel´eg´ıt´es´et. Az [1] dolgozatban k´et modellt vizsg´alnak, az egyikben a szervernek vissza kell t´ernie a k´er´essorozat v´eg´en a kezd˝opontba a m´asikban nem. Az els˝o modellben optim´alis 2-kompetit´ıv algoritmust adtak az ´altal´anos esetre, ´es egy 1.75kompetit´ıv algoritmust, tov´abb´a egy 1.64 als´o korl´atot a lehets´eges kompetit´ıv h´anyadosokra az egyenes eset´en. A m´asodik modellben 2.5-kompetit´ıv algoritmust mutattak be ´altal´anos t´er eset´en ´es 7/3-kompetit´ıv algoritmust az egyenesre. Ez a probl´ema jelenleg igen nagy ´erdekl˝od´esre tart sz´amot. T¨obb eredm´eny sz¨ uletett m´as c´elf¨ uggv´enyekre a legt¨obb a k´er´esek kiel´eg´ıt´es´enek ´atlagos idej´ere (ld [12] ´es az ott szerepl˝o hivatkoz´asok). Az ¨osszes dolgozat egyetlen szerver eset´et vizsg´alja, arra az esetre, amelyben t¨obb szerver haszn´alhat´o nem ismertek eredm´enyek. Fuvarra v´ arva modellek: V´eg¨ ul mindenk´eppen ´erdemes megeml´ıten¨ unk ezt a v´altozatot is. A fenti modellekben a k´er´esek egy pontra vonatkoztak, ahova a szervert k¨ uldeni kellett. M´asr´eszt igen sok gyakorlati alkalmaz´as eset´en a k´er´est nem lehet kiel´eg´ıteni puszt´an az´altal, hogy odak¨ uld¨ unk egy szervert, hanem a k´er´es arra vonatkozik, hogy adott pontb´ol sz´all´ıtsunk 3
el valamit egy m´asik pontba. T¨obb online modellt tanulm´anyoztak att´ol f¨ ugg˝oen, hogy a c´el´allom´ast is megkapja az algoritmus a k´er´es ´erkez´esekor vagy csak akkor amikor oda´erkezett a k´er´es helysz´ın´ere. Irodalomjegyz´ ek [1] G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo, Algorithms for the On-Line Travelling Salesman, Algorithmica, 29, 560–581, 2001. [2] N. Auscheuer, S. O. Krumke, J. Rambau, Online dial a ride problems: Minimizing the completion time, Proc. of the 17-th International Symposiumon Theoretical Aspects of Computer Science, LNCS 1770, Springer Verlag, 639–650, 2000. [3] M. Chrobak, L. Larmore, An optimal algorithm for k-servers on trees, SIAM Journal on Computing, 20, 144-148, 1991. [4] M. Chrobak, L. Larmore, The server problem and online games, DIMACS series in Discrete mathemtaics and Theortical Computer Science, 7, 11–64, 1992. [5] M. Chrobak, L. Larmore, Metrical task systems, the server problem and the work function algorithm, Online algorithms: The State of the Art (A. Fiat, and G. J. Woeginger (eds.)) LNCS 1442, Springer-Verlag, 74–96, 1998. [6] M. Chrobak, J. Sgall, The weighted 2-server Problem, Proc. of the 17-th International Symposiumon Theoretical Aspects of Computer Science, LNCS 1770, Springer-Verlag, 593–604, 2000. [7] L. Epstein, Cs. Imreh, R. van Stee, More on weighted servers or FIFO is better than LRU, Proceedings of 27th MFCS, LNCS 2420 Springer, 257–268, 2002 [8] A. Fiat, Y. Rabani, Y. Ravid, Competitive k-server algorithms, Journal of Computer and System Sciences, 48, 410-428, 1994. (also in FOCS 90) [9] A. Fiat, M. Ricklin, Competitive algorithms for the weighted server problem, Theoretical Computer Science, 130 85–99, 1994. [10] S. Irani, Competitive analysis of paging, Online algorithms: The State of the Art (A. Fiat, and G. J. Woeginger (eds.)) LNCS 1442, Springer-Verlag, 52–73, 1998 [11] E. Koutsoupias, C. Papadimitriou, On the k-server conjecture, Journal of the ACM, 42, 971–983, 1995.
4
[12] S. O. Krumke, W. E. de Paepe, D. Poengsen, L. Stougie, News from the Online Traveling Repairman, Proceedings of 26th MFCS, LNCS 2136 Springer, 487–499, 2001. [13] M. Manasse, L. McGeoch, D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, 11, 208–230, 1990
5
