Elias Koutsoupias
Abstract
We prove that the work function algorithm for the k-server problem has a competitive ratio at most 2k−1. Manasse et al. [1988] conjectured that the competitive ratio for the k-server problem is exactly k (it is trivially at least k); previously the best-known upper bound was exponential in k. Our proof involves three crucial ingredients: A quasiconvexity property of work functions, a duality lemma that uses quasiconvexity to characterize the configuration that achieve maximum increase of the work function, and a potential function that exploits the duality lemma.
- ~BEN-DAVID, S., BORODIN, A., KARP, R., TARDOS, G., AND WIGDERSON, A. 1994. On the power ~of randomization in on-line algorithms. Algorlthmzca 11, 1 (Jan.), 2-14.Google Scholar
- ~BERMAN, P., KARLOFF, H. J., AND TARDOS, G. 1990. A competitive three-server algorithm. In ~Proceedzngs of the 1st Annual ACM-S1AM Symposlt~m on Discrete Algorithms. ACM, New York, ~pp. 280-290. Google Scholar
- ~BLUM, A., KARLOFF, H., RABANI, Y., AND SAKS, M. 1992. A decomposition theorem and ~bounds for randomized server problems. In Proceedings of the 33rd Annual Symposium on ~Foundations of Computer Science. IEEE, New York, pp. 197-207.Google Scholar
- ~BURLEY, W.R. 1993. Traversing layered graphs using the work function algorithm. Tech. Rep. ~CS93-319. Dept. of Computer Science and Engineering. Unw. of Cahfornia at San Diego, San ~Diego, Calif.Google Scholar
- ~CHROBAK, M., KARLOFF, H. J., PAYNE, T., AND VISHWANATHAN, S. 1991. New results on server ~problems. SIAM ff. Disc. Math. 4, 172 181. Google Scholar
- ~CHROBAK, M., AND LARMORE, L.k. 1991a. An optimal on-line algorithm for k-servers on trees. ~SIAMJ. Comput. 20, i (Feb.), 144-148. Google Scholar
- ~CHROBAK, M., AND LARMORE, L.L. 1991b. On fast algorithms for two servers. J. Algorithms ~12, 4 (Dec.), 607-614. Google Scholar
- ~CHROBAK, M., AND LARMORE, L.L. 1992a. Harmonic is 3-competitive for two servers. Theoret. ~Compztt. Sci. 98, 2 (May), 339-346. Google Scholar
- ~CHROBAK, M., AND LARMORE, L.L. 1992b. The server problem and ondme games. In On-Line ~Algolfthms: Proceedings of a DIMACS Workshop. DIMACS Series in Discrete Mathematics and ~Theoretical Computer Science, vol. 7. ACM, New York, pp. 11-64.Google Scholar
- ~CHROBAK, M., AND LARMORE, k.k. 1994. Generosity helps or an ll-competitive algorithm for ~three servers. J. Algor. 16, 2 (Mar.) 234-263. Google Scholar
- ~CHROBAK, M., LARMORE, L. L., REINGOLD, N., AND WESTBROOK, J. 1993. Page migration ~algorithms using work functions. In Proceedings of the 4th I~ltemational Symposium o~z Algo- ~rithms and Computarion. Lecture Notes in Computer Science. Springer-Verlag, New York, ~pp. 406 415. Google Scholar
- ~COPPERSMITH, D. DOYLE, P., RAGHAVAN, P., AND SNIR, M. 1993. Random walks on weighted ~graphs and applications to on-line algorithms J. ACM 40, 3 (July), 421-453. Google Scholar
- ~FIAT, A., RABANI, Y., AND RAVID, Y. 1990. Competitive k-server algorithms. In Proceedltzgs of ~the 31st Annual Symposium on Foundations of Computer Science. vol. 2. IEEE, New York, ~pp. 454 463.Google Scholar
- ~FIAT, A., RABANI, Y., RAVID, Y., AND 8CHIEBER, B. 1994. A deterministic O(k3)-competitive ~k-server algorithm for the circle. Algonthmiea 11, 6 (June), 572-578.Google Scholar
- ~GROVE, E. 1991. The Harmonic online k-server algorithm is competitive. In Proceedings of the ~23rd Anmtal ACM Symposium on Theory of Computing (New Orleans, La., May 6-8). ACM, ~New York, pp. 260-266. Google Scholar
- IRANI, S., AND RUBINFELD, R. 1991. A competitive 2-server algorithm, htf. Proc. Lett. 39, 2 ~(July), 85-91. Google Scholar
- ~KARLIN, A. R., MANASSE, M. S., McGEOCH, L. A., AND OWtCKI, S. 1994. Competitive random- ~ized algorithms for nonuniform problems. Algorithmica 11, 6 (June), 542-571.Google Scholar
- ~KARLOFF, H., RABANX, Y., AND RAVID, Y. t994. Lower bounds for randomized k-server and ~motion-planning algorithms. SIAM J. Comp,t. 23, 2 (Apr.), 293-312. Google Scholar
- ~KOUTSOUmaS, E. 1994. On-line algorithms and the k-server conjecture. Ph.D. dissertation. ~Univ. Calif. at San Diego, La Jolla, Calif. Google Scholar
- ~KOUTSOUPIAS, E., AND PAPADIMITRIOU, C.H. 1994. On the k-server conjecture. In Proceedttzgs ~of the 26th Annual ACM Symposium on Theory of Co,zputing (Montreal, Que., Canada, May ~23-25). ACM, New York, pp. 507-51l. Google Scholar
- KOUTSOUPIAS, E., AND PAPADIMITRIOU, C.H. The 2-evader problem. In preparation.Google Scholar
- KOUTSOUPIAS, E., AND PAPADIM1TRIOU, C.H. 1994. Beyond competitive analysis. In Proceed- ~ings of the 35th IEEE Symposium on Foundations of Comptttet' Sicience (FOCS). IEEE, New ~York, 394-400.Google Scholar
- ~MANASSE, M. S., McGEOCH, L.A., AND SLEATOR, D. D. 1988. Competitive algorithms for ~on-line problems. In Proceedings 20th Antmal ACM Symposium on Theory of Compztting ~(Chicgao, IlL, May 2-4). ACM New York, pp. 322-333. Google Scholar
- ~MANASSE, M. S., MCGEOCH, L. A., AND SLEATOR, D. D. 1990. Competitive algorithms for ~server problems. J. Algorithms 11, 2 (June), 208-230. Google Scholar
- ~SLEATOR, D. D., AND TARJAN, R.E. 1985. Amortized efficiency of list update and paging rules. ~Commun. ACM 28, 2 (Feb.), 202-208. Google Scholar
Index Terms
- On the k-server conjecture
Recommendations
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 ...
A new upper bound on the work function algorithm for the k-server problem
AbstractThe k-server problem was introduced by Manasse et al. (in: Proceedings of the 20th annual ACM symposium on theory of computing, Chicago, Illinois, USA, pp 322–333, 1988), and is one of the most famous and well-studied online problems. Koutsoupias ...
Online Results for Black and White Bin Packing
In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each ...
Comments