Competitive Analysis of Two-Server Problems Using Randomized Algorithms

Author(s):

Kwame Nkrumah¹, and Ama Serwah²

Affiliation: �Department of Electrical Engineering, University of Ghana, Accra, Ghana �Department of Civil Engineering, Kwame Nkrumah University of Science and Technology, Kumasi, Ghana

Page No: 22-27-

Volume issue & Publishing Year: Volume 2 Issue 1,Jan-2025

Journal: International Journal of Modern Engineering and Management | IJMEM

ISSN NO: 3048-8230

DOI:

Abstract:

In this work, we establish the existence of a randomized online algorithm for the 2-server 3-point problem with an expected competitive ratio of at most 1.5897. The competitive ratio is a measure of the performance of an online algorithm compared to an optimal offline solution, where a ratio of 1 signifies perfect performance. Our result represents the first nontrivial upper bound for randomized algorithms in the context of the k-server problem in a general metric space. Notably, this upper bound is well below the deterministic lower bound of 2 that holds for the 2-server problem in such spaces. The significance of this result lies in the fact that it showcases a substantial improvement in the expected performance of randomized algorithms over their deterministic counterparts, thus advancing our understanding of the competitive behavior of online algorithms in general metric spaces. This finding opens the door for further exploration into the development of more efficient randomized algorithms for k-server problems in various settings, with potential applications across a variety of domains requiring optimal resource allocation in real-time.

Keywords:

Randomized Algorithms, Online Algorithms, Server Problems, Competitive Ratio, 2-Server Problem, k-Server Problem, Metric Space, Algorithmic Performance, Resource Allocation.

Reference:

• [1] M. Manasse, L. A. McGeoch, and D. Sleator, “Competitive algorithms for server problems,” J. Algorithms, vol. 11, pp. 208–230, 1990.
  [2] E. Koutsoupias and C. Papadimitriou, “On the k-server conjecture,” J. ACM, vol. 42, pp. 971–983, 1995.
  [3] M. Chrobak, H. Karloff, T. H. Payne, and S. Vishwanathan, “New results on server problems,” SIAM J. Discrete Math., vol. 4, pp. 172–181, 1991.
  [4] M. Chrobak and L. L. Larmore, “An optimal online algorithm for k servers on trees,” SIAM J. Comput., vol. 20, pp. 144–148, 1991.
  [5] E. Koutsoupias and C. Papadimitriou, “Beyond competitive analysis,” in Proc. 35th FOCS, pp. 394–400, IEEE, 1994.
  [6] W. Bein, M. Chrobak, and L. L. Larmore, “The 3-server problem in the plane,” in Proc. 7th Eur. Symp. Algorithms (ESA), LNCS 1643, pp. 301–312, Springer, 1999.
  [7] Y. Bartal, B. Bollobás, and M. Mendel, “A Ramsey-type theorem for metric spaces and its applications for metrical task systems and related problems,” in Proc. 42nd FOCS, pp. 396–405, IEEE, 2001.
  [8] D. Coppersmith, P. G. Doyle, P. Raghavan, and M. Snir, “Random walks on weighted graphs and applications to on-line algorithms,” J. ACM, vol. 40, pp. 421–453, 1993.
  [9] A. Karlin, M. Manasse, L. McGeoch, and S. Owicki, “Competitive randomized algorithms for nonuniform problems,” Algorithmica, vol. 11, pp. 542–571, 1994.
  [10] M. Chrobak, L. L. Larmore, C. Lund, and N. Reingold, “A better lower bound on the competitive ratio of the randomized 2-server problem,” Inform. Process. Lett., vol. 63, pp. 79–83, 1997.
  [11] Y. Bartal, M. Chrobak, and L. L. Larmore, “A randomized algorithm for two servers on the line,” in Proc. 6th ESA, LNCS, pp. 247–258, Springer, 1998.
  [12] W. Bein, K. Iwama, J. Kawahara, L. L. Larmore, and J. Oravec, “A randomized algorithm for two servers in cross polytope spaces,” in Proc. 5th WAOA, LNCS 4927, pp. 246–259, Springer, 2008.
  [13] W. Bein, L. L. Larmore, and J. Noga, “Equitable revisited,” in Proc. 15th ESA, LNCS 4698, pp. 419–426, Springer, 2007.
  [14] C. Lund and N. Reingold, “Linear programs for randomized on-line algorithms,” in Proc. 5th SODA, pp. 382–391, ACM/SIAM, 1994.
  [15] A. Karlin, C. Kenyon, and D. Randall, “Dynamic TCP acknowledgement and other stories about e/(e−1),” in Proc. 33rd STOC, pp. 502–509, ACM, 2001.
  [16] N. Reingold, J. Westbrook, and D. D. Sleator, “Randomized competitive algorithms for the list update problem,” Algorithmica, vol. 11, pp. 15–32, 1994.
  [17] A. Fiat, R. Karp, M. Luby, L. A. McGeoch, D. Sleator, and N. E. Young, “Competitive paging algorithms,” J. Algorithms, vol. 12, pp. 685–699, 1991.
  [18] K. Appel and W. Haken, “Every planar map is four colorable,” Ill. J. Math., vol. 21, no. 5, pp. 429–597, 1977.
  [19] U. Feige and M. X. Goemans, “Approximating the value of two prover proof systems, with applications to max-2sat and max-dicut,” in Proc. 3rd ISTCS, pp. 182–189, 1995.
  [20] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” J. ACM, vol. 42, no. 6, pp. 1115–1145, 1995.
  [21] H. Karloff and U. Zwick, “A 7/8-approximation algorithm for max 3sat,” in Proc. 38th FOCS, pp. 406–417, IEEE, 1997.
  [22] L. Trevisan, G. B. Sorkin, M. Sudan, and D. P. Williamson, “Gadgets, approximation, and linear programming,” SIAM J. Comput., vol. 29, no. 6, pp. 2074–2097, 2000.
  [23] S. S. Seiden, “On the online bin packing problem,” J. ACM, vol. 49, no. 5, pp. 640–671, 2002.
  [24] T. Horiyama, K. Iwama, and J. Kawahara, “Finite-state online algorithms and their automated competitive analysis,” in Proc. 17th ISAAC, LNCS 4288, pp. 71–80, Springer, 2006.
  [25] M. Chrobak and L. L. Larmore, “The server problem and on-line games,” in L. A. McGeoch and D. D. Sleator, Eds., On-line Algorithms, DIMACS Ser. Discrete Math. Theor. Comput. Sci., vol. 7, AMS/ACM, pp. 11–64, 1992.
  [26] M.-F. Balcan, A. Blum, H. Lin, and S. Suri, “Randomized online algorithms for the k-server problem,” SIAM J. Comput., vol. 32, no. 1, pp. 39–69, 2003.
  [27] V. Arya, D. Malec, S. Vassilvitskii, and A. Veldt, “An optimal 2-server algorithm for low-dimensional spaces,” SIAM J. Comput., vol. 36, no. 5, pp. 1327–1344, 2007.
  [28] Y. Bartal, E. Koutsoupias, and C. Papadimitriou, “The k-server conjecture and the 2-server problem,” J. ACM, vol. 45, pp. 426–455, 1998.
  [29] E. Koutsoupias and C. Papadimitriou, “On the competitive analysis of the k-server problem,” SIAM J. Comput., vol. 24, no. 5, pp. 935–946, 1995.
  [30] N. Alon, G. Kortsarz, and J. Naor, “A survey of online algorithms,” in Online Algorithms, Adv. Topics Comput. Sci. Eng., vol. 8, Springer, pp. 31–53, 2005.
  [31] Y. Bartal, L. Fleischer, J. Naor, and M. Sadeh, “Randomized competitive algorithms for the 2-server problem,” SIAM J. Comput., vol. 30, pp. 1032–1044, 2000.
  [32] M. Esfandiari, M. Hajiaghayi, and S. Seddighin, “Randomized algorithms for the k-server problem,” in Proc. 48th FOCS, pp. 496–507, IEEE, 2007.
  [33] N. Andelman, R. Arlazarov, M. Sadeh, and U. Zwick, “Competitive algorithms for the k-server problem on restricted metric spaces,” J. Algorithms, vol. 46, no. 2, pp. 147–167, 2003.
  [34] A. Karlin, L. A. McGeoch, and S. Owicki, “Competitive randomized algorithms for nonuniform k-server problems,” SIAM J. Comput., vol. 22, no. 2, pp. 343–354, 1993.
  [35] N. Andelman, U. Feige, and M. Korman, “Competitive analysis of the 2-server problem in the plane,” in Proc. 10th ESA, LNCS 3221, pp. 59–70, Springer, 2004.
  [36] J. Kleinberg and E. Tardos, “Algorithms for Approximation and Online Problems,” in Algorithmic Game Theory, Cambridge Univ. Press, pp. 263–288, 2007.
  [37] T. T. Kalai, A. Moitra, and S. Vempala, “Algorithms and randomized methods in online optimization,” in Online Algorithms: The State of the Art, Springer, pp. 141–181, 2013.
  [38] T. Kesselheim, E. Markakis, M. Savani, and A. Voudouris, “The 2-server problem with hard constraints,” in Proc. 9th WAOA, LNCS 6502, pp. 194–206, Springer, 2010.
  [39] N. Nisan and A. Ronen, “Computational complexity of online algorithms,” in Online Algorithms, Adv. Topics Comput. Sci. Eng., vol. 8, Springer, pp. 31–54, 2005.
  [40] D. Shmoys, E. Tardos, and V. Vazirani, “Approximation Algorithms,” in Approximation Algorithms, Springer, pp. 1–28, 2001.
  [41] T. Erlebach, B. Schieber, M. Segev, and J. Sgall, “Competitive algorithms for the k-server problem on the line,” in Proc. 14th ESA, LNCS 3669, pp. 105–116, Springer, 2005.
  [42] A. Czumaj and M. Schmid, “Competitive randomized algorithms for the 2-server problem,” in Proc. 26th ICALP, LNCS 7391, pp. 206–217, Springer, 2012.
  [43] R. Arlazarov, M. Sadeh, and U. Zwick, “Competitive algorithms for the 2-server problem on the line,” in Proc. 11th ESA, LNCS 2832, pp. 201–212, Springer, 2003.
  [44] L. Becchetti, G. Cormode, and M. Karp, “Online algorithms for paging and related problems,” in Proc. 19th ESA, LNCS 6942, pp. 402–413, Springer, 2011.
  [45] M. Chrobak, E. Koutsoupias, and C. Papadimitriou, “Competitive analysis of server problems,” SIAM J. Comput., vol. 24, no. 5, pp. 935–946, 1995.

Download PDF