Sébastien Bubeck
ABSTRACT
We present an O((logk)2)-competitive randomized algorithm for the k-server problem on hierarchically separated trees (HSTs). This is the first o(k)-competitive randomized algorithm for which the competitive ratio is independent of the size of the underlying HST. Our algorithm is designed in the framework of online mirror descent where the mirror map is a multiscale entropy. When combined with Bartal’s static HST embedding reduction, this leads to an O((logk)2 logn)-competitive algorithm on any n-point metric space. We give a new dynamic HST embedding that yields an O((logk)3 logΔ)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most Δ.
Supplemental Material
- {ABBS10} Jacob Abernethy, Peter Bartlett, Niv Buchbinder, and Isabelle Stanton. A regularization approach to metrical task systems. In Algorithmic Learning Theory, ALT 2010. Springer, 2010. Google Scholar
Digital Library
- {Bar96} Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184–193, 1996. Google ScholarDigital Library
- {Bar98} Yair Bartal. On approximating arbitrary metrices by tree metrics. In STOC ’98 (Dallas, TX), pages 161–168. ACM, New York, 1998. Google ScholarDigital Library
- STOC’18, June 25–29, 2018, Los Angeles, CA, USA Bubeck, Cohen, Lee, Lee, and MądryGoogle Scholar
- {BBK99} Avrim Blum, Carl Burch, and Adam Kalai. Finely-competitive paging. In 40th Annual Symposium on Foundations of Computer Science (New York, 1999), pages 450–457. IEEE Computer Soc., Los Alamitos, CA, 1999. Google ScholarDigital Library
- {BBM06} Yair Bartal, Béla Bollobás, and Manor Mendel. Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. System Sci., 72(5):890–921, 2006. Google ScholarDigital Library
- {BBMN15} Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic-competitive algorithm for the k-server problem. J. ACM, 62(5):Art. 40, 49, 2015. Google ScholarDigital Library
- {BBN12} Nikhil Bansal, Niv Buchbinder, and Joseph Naor. A primal-dual randomized algorithm for weighted paging. J. ACM, 59(4):Art. 19, 24, 2012. Google ScholarDigital Library
- {BCN14} Niv Buchbinder, Shahar Chen, and Joseph (Seffi) Naor. Competitive analysis via regularization. In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, pages 436–444, Philadelphia, PA, USA, 2014. Society for Industrial and Applied Mathematics. Google ScholarDigital Library
- {BE98} Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, New York, 1998. Google ScholarDigital Library
- {BKRS00} Avrim Blum, Howard Karloff, Yuval Rabani, and Michael Saks. A decomposition theorem for task systems and bounds for randomized server problems. SIAM J. Comput., 30(5):1624–1661, 2000. Google ScholarDigital Library
- {BLMN05} Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric Ramsey-type phenomena. Ann. of Math. (2), 162(2):643–709, 2005.Google ScholarCross Ref
- {Bub15} Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231–357, 2015.Google ScholarDigital Library
- {CKPV91} M. Chrobak, H. Karloff, T. Payne, and S. Vishwanathan. New results on server problems. SIAM J. Discrete Math., 4(2):172–181, 1991. Google ScholarDigital Library
- {CL91} Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm for k servers on trees. SIAM J. Comput., 20(1):144–148, 1991. Google ScholarDigital Library
- {CMP08} Aaron Coté, Adam Meyerson, and Laura Poplawski. Randomized k-server on hierarchical binary trees. In STOC’08, pages 227–233. ACM, New York, 2008. Google ScholarDigital Library
- {FKL + 91} A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and Young N. E. Competitive paging algorithms. J. Algorithms, 12(4):685–699, 1991. Google ScholarDigital Library
- {FRT04} Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485–497, 2004. Google ScholarDigital Library
- {Haz16} Elad Hazan. Introduction to online convex optimization. Foundations and TrendsÂő in Optimization, 2(3-4):157–325, 2016.Google ScholarDigital Library
- {Kou09} Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105–118, 2009. Google ScholarDigital Library
- {KP95} Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. J. Assoc. Comput. Mach., 42(5):971–983, 1995. Google ScholarDigital Library
- {KRN65} K. Kuratowski and C. Ryll-Nardzewski. A general theorem on selectors. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 13:397–403, 1965.Google Scholar
- {KRR94} Howard Karloff, Yuval Rabani, and Yiftach Ravid. Lower bounds for randomized k-server and motion-planning algorithms. SIAM J. Comput., 23(2):293–312, 1994. Google ScholarDigital Library
- {MMS90} Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for server problems. J. Algorithms, 11(2):208–230, 1990. Google ScholarDigital Library
- {MS91} Lyle A. McGeoch and Daniel D. Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6(6):816–825, 1991. Google ScholarDigital Library
- {NY83} A. Nemirovski and D. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley Interscience, 1983.Google Scholar
Index Terms
- k-server via multiscale entropic regularization
Recommendations
Competitive k-server algorithms
Special issue: 31st IEEE conference on foundations of computer science, Oct. 22–24, 1990In this paper we give deterministic competitive k-server algorithms for all k and all metric spaces. This settles the k-server conjecture up to the competitive ratio. The best previous result for general metric spaces was a three-server randomized ...
Range mode and range median queries in constant time and sub-quadratic space
Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time. For the function mode we improve the previously known space bound O(n^2/logn) to O(n^2loglogn/...
The (h,k)-Server Problem on Bounded Depth Trees
Special Issue on Soda'17 and Regular PapersWe study the k-server problem in the resource augmentation setting, i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with h ≤ k servers. The problem is very poorly understood beyond uniform ...
Comments