{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T18:55:36Z","timestamp":1775242536431,"version":"3.50.1"},"reference-count":94,"publisher":"Emerald","issue":"2-3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,5,15]]},"abstract":"<jats:p>The primal\u2014dual method is a powerful algorithmic technique that has proved to be extremely useful for a wide variety of problems in the area of approximation algorithms for NP-hard problems. The method has its origins in the realm of exact algorithms, e.g., for matching and network flow. In the area of approximation algorithms, the primal\u2014dual method has emerged as an important unifying design methodology, starting from the seminal work of Goemans and Williamson [60]<\/jats:p>\n                  <jats:p>We show in this survey how to extend the primal\u2014dual method to the setting of online algorithms, and show its applicability to a wide variety of fundamental problems. Among the online problems that we consider here are the weighted caching problem, generalized caching, the set-cover problem, several graph optimization problems, routing, load balancing, and the problem of allocating ad-auctions. We also show that classic online problems such as the ski rental problem and the dynamic TCP-acknowledgement problem can be solved optimally using a simple primal\u2014dual approach.<\/jats:p>\n                  <jats:p>The primal\u2014dual method has several advantages over existing methods. First, it provides a general recipe for the design and analysis of online algorithms. The linear programming formulation helps detecting the difficulties of the online problem, and the analysis of the competitive ratio is direct, without a potential function appearing \"out of nowhere.\" Finally, since the analysis is done via duality, the competitiveness of the online algorithm is with respect to an optimal fractional solution, which can be advantageous in certain scenarios.<\/jats:p>","DOI":"10.1561\/0400000024","type":"journal-article","created":{"date-parts":[[2009,5,26]],"date-time":"2009-05-26T03:13:33Z","timestamp":1243307613000},"page":"93-263","source":"Crossref","is-referenced-by-count":201,"title":["The Design of Competitive Online Algorithms via a Primal\u2014Dual Approach"],"prefix":"10.1561","volume":"3","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[{"name":"Technion \u2014 Israel Institute of Technology Computer Science Department, ,","place":["Israel"]}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion \u2014 Israel Institute of Technology Computer Science Department, ,","place":["Israel"]}]}],"member":"140","published-online":{"date-parts":[[2009,5,15]]},"reference":[{"issue":"234-1","key":"2026040314032777300_ref001","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0304-3975(98)00116-9","article-title":"Competitive analysis of randomized paging algorithms","volume":"234","author":"Achlioptas","year":"2000","journal-title":"Theory Computer Science"},{"key":"2026040314032777300_ref002","first-page":"31","article-title":"Page replacement for general caching problems","author":"Albers","year":"1999","journal-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314032777300_ref003","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1145\/780542.780558","article-title":"The online set cover problem","author":"Alon","year":"2003","journal-title":"Proceedings of the 35th Annual ACM Symposium on the Theory of Computation"},{"issue":"4","key":"2026040314032777300_ref004","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/1198513.1198522","article-title":"A general approach to online network optimization problems","volume":"2","author":"Alon","year":"2006","journal-title":"ACM Transactions on Algorithms"},{"key":"2026040314032777300_ref005","first-page":"238","article-title":"Admission control to minimize rejections and online set cover with repetitions","author":"Alon","year":"2005","journal-title":"Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures"},{"key":"2026040314032777300_ref006","author":"Alon","journal-title":"The Probabilistic Method"},{"key":"2026040314032777300_ref007","first-page":"26","article-title":"Auctions with budget constraints","author":"Andelman","year":"2004","journal-title":"Proceedings of the 9th Scandinavian Workshop on Algorithm Theory"},{"issue":"3","key":"2026040314032777300_ref008","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1145\/258128.258201","article-title":"On-line routing of virtual circuits with applications to load balancing and machine scheduling","volume":"44","author":"Aspnes","year":"1997","journal-title":"Journal of the ACM"},{"key":"2026040314032777300_ref009","first-page":"68","article-title":"On-line generalized Steiner problem","author":"Awerbuch","year":"1996","journal-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314032777300_ref010","first-page":"519","article-title":"Making commitments in the face of uncertainty: How to pick a winner almost every time","author":"Awerbuch","year":"1996","journal-title":"Proceedings of the 28th Annual ACM Symposium on Theory of Computing"},{"key":"2026040314032777300_ref011","first-page":"32","article-title":"Throughput-competitive online routing","author":"Awerbuch","year":"1993","journal-title":"Proceedings of the 34th Symposium on Foundations of Computer Science"},{"key":"2026040314032777300_ref012","article-title":"On-line load balancing","author":"Azar","journal-title":"Online Algorithms \u2014 The State of the Art"},{"key":"2026040314032777300_ref013","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/jagm.1995.1008","article-title":"The competitiveness of on-line assignments","volume":"18","author":"Azar","year":"1995","journal-title":"Journal of Algorithms"},{"key":"2026040314032777300_ref014","first-page":"507","article-title":"A primal-dual randomized algorithm for weighted paging","author":"Bansal","year":"2007","journal-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314032777300_ref015","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/1374376.1374412","article-title":"Randomized competitive algorithms for generalized caching","author":"Bansal","year":"2008","journal-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing"},{"issue":"5","key":"2026040314032777300_ref016","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1145\/502102.502107","article-title":"A unified approach to approximating resource allocation and scheduling","volume":"48","author":"Bar-Noy","year":"2001","journal-title":"Journal of the ACM"},{"key":"2026040314032777300_ref017","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","article-title":"A linear-time approximation algorithm for the weighted vertex cover problem","volume":"2","author":"Bar-Yehuda","year":"1981","journal-title":"Journal of Algorithms"},{"key":"2026040314032777300_ref018","first-page":"396","article-title":"A Ramsey-type theorem for metric spaces and its applications for metrical task systems and related problems","author":"Barta","journal-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314032777300_ref019","first-page":"711","article-title":"A polylog(n)-competitive algorithm for metrical task systems","author":"Bartal","year":"1997","journal-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing"},{"key":"2026040314032777300_ref020","first-page":"463","article-title":"On metric Ramsey-type phenomena","author":"Bartal","year":"2003","journal-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing"},{"issue":"2","key":"2026040314032777300_ref021","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.jalgor.2004.06.002","article-title":"Randomized k-server algorithms for growth-rate bounded graphs","volume":"55","author":"Bartal","year":"2005","journal-title":"Journal of Algorithms"},{"key":"2026040314032777300_ref022","first-page":"344","article-title":"On-line algorithms for Steiner tree problems","author":"Berman","year":"1997","journal-title":"Proceedings of the 29th Annual ACM Symposium on the Theory of Computation"},{"key":"2026040314032777300_ref023","author":"Bertsekas","journal-title":"Data Networks"},{"key":"2026040314032777300_ref024","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1109\/SFFCS.1999.814617","article-title":"Finely-competitive paging","author":"Blum","year":"1999","journal-title":"IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314032777300_ref025","article-title":"What to do with your free time: Algorithms for infrequent requests and randomized weighted caching","author":"Blum"},{"key":"2026040314032777300_ref026","article-title":"Near-optimal online auctions","author":"Blum","year":"2005","journal-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314032777300_ref027","first-page":"44","article-title":"Multi-unit auctions with budget-constrained bidders","author":"Borgs","year":"2005","journal-title":"Proceedings of the 6th ACM Conference on Electronic Commerce"},{"key":"2026040314032777300_ref028","volume-title":"Online Computation and Competitive Analysis","author":"Borodin","year":"1998"},{"issue":"4","key":"2026040314032777300_ref029","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1145\/146585.146588","article-title":"An optimal on-line algorithm for metrical task system","volume":"39","author":"Borodin","year":"1992","journal-title":"Journal of the ACM"},{"key":"2026040314032777300_ref030","first-page":"253","article-title":"Online primal-dual algorithms for maximizing ad-auctions revenue","author":"Buchbinder","year":"2007","journal-title":"Proceedings of the 15th Annual European Symposium"},{"key":"2026040314032777300_ref031","first-page":"952","article-title":"Online make-to-order joint replenishment model: Primal dual competitive algorithms","author":"Buchbinder","year":"2008","journal-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314032777300_ref032","article-title":"Online primal-dual algorithms for covering and packing problems","author":"Buchbinder","year":"2005","journal-title":"Proceedings of the 13th Annual European Symposium on Algorithms"},{"key":"2026040314032777300_ref033","doi-asserted-by":"crossref","article-title":"Improved bounds for online routing and packing via a primal-dual approach","author":"Buchbinder","DOI":"10.1109\/FOCS.2006.39"},{"key":"2026040314032777300_ref034","article-title":"Fair online load balancing","author":"Buchbinder","year":"2006","journal-title":"Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures"},{"key":"2026040314032777300_ref035","article-title":"Cost-aware WWW proxy caching algorithms","author":"Cao"},{"key":"2026040314032777300_ref036","first-page":"106","article-title":"Strengthening integrality gaps for capacitated network design and covering problems","author":"Carr","year":"2000","journal-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314032777300_ref037","first-page":"532","article-title":"Set connectivity problems in undirected graphs and the directed steiner network problem","author":"Chekuri","year":"2008","journal-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"3","key":"2026040314032777300_ref038","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1137\/S0895480101396937","article-title":"A linear programming formulation and approximation algorithms for the metric labeling problem","volume":"18","author":"Chekuri","year":"2005","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2026040314032777300_ref039","first-page":"156","article-title":"The all-or-nothing multicommodity flow problem","author":"Chekuri","year":"2004","journal-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing"},{"issue":"2","key":"2026040314032777300_ref040","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1137\/0404017","article-title":"New results on server problems","volume":"4","author":"Chrobak","year":"1991","journal-title":"SIAM Journal on Discrete Mathmatics"},{"key":"2026040314032777300_ref041","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set-covering problem","author":"Chvatal","year":"1979","journal-title":"Mathematics of Operations Research"},{"key":"2026040314032777300_ref042","author":"Chvatal","journal-title":"Linear Programming"},{"key":"2026040314032777300_ref043","first-page":"879","article-title":"LP-based analysis of greedy-dual-size","author":"Cohen","year":"1999","journal-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"1","key":"2026040314032777300_ref044","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1002\/rsa.20124","article-title":"A randomized on-line algorithm for the k-server problem on a line","volume":"29","author":"Csaba","year":"2006","journal-title":"Random Structures and Algorithms"},{"key":"2026040314032777300_ref045","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/375827.375843","article-title":"On-line analysis of the TCP acknowledgement delay problem","volume":"48","author":"Dooly","year":"2001","journal-title":"Journal of the ACM"},{"key":"2026040314032777300_ref046","first-page":"448","article-title":"A tight bound on approximating arbitrary metrics by tree metrics","author":"Fakcharoenphol","year":"2003","journal-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing"},{"issue":"4","key":"2026040314032777300_ref047","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of in for approximating set cover","volume":"45","author":"Feige","year":"1998","journal-title":"Journal of the ACM"},{"issue":"4","key":"2026040314032777300_ref048","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","article-title":"Competitive paging algorithms","volume":"12","author":"Fiat","year":"1991","journal-title":"Journal of Algorithms"},{"issue":"6","key":"2026040314032777300_ref049","doi-asserted-by":"crossref","first-page":"1403","DOI":"10.1137\/S0097539700376159","article-title":"Better algorithms for unfair metrical task systems and applications","volume":"32","author":"Fiat","year":"2003","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"2026040314032777300_ref050","doi-asserted-by":"crossref","first-page":"1403","DOI":"10.1137\/S0097539700376159","article-title":"Better algorithms for unfair metrical task systems and applications","volume":"32","author":"Fiat","year":"2003","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"2026040314032777300_ref051","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1016\/S0022-0000(05)80060-1","article-title":"Competitive k-server algorithms","volume":"48","author":"Fiat","year":"1994","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314032777300_ref052","first-page":"1001","article-title":"A fast approximation scheme for fractional covering problems with variable upper bounds","author":"Fleischer","year":"2004","journal-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"4","key":"2026040314032777300_ref053","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0895480199355754","article-title":"Approximating fractional multicommodity flow independent of the number of commodities","volume":"13","author":"Fleischer","year":"2000","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2026040314032777300_ref054","first-page":"371","article-title":"Fractional covering with upper bounds on the variables: Solving LPs with negative entries","author":"Garg","year":"2004","journal-title":"Proceedings of the 12th European Symposium on Algorithms"},{"key":"2026040314032777300_ref055","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1109\/SFCS.1998.743463","article-title":"Faster and simpler algorithms for multicommodity flow and other fractional packing problems","author":"Garg","year":"1998","journal-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science"},{"issue":"1","key":"2026040314032777300_ref056","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1006\/jagm.2000.1096","article-title":"A polylogarithmic approximation algorithm for the group steiner tree problem","volume":"37","author":"Garg","year":"2000","journal-title":"Journal of Algorithms"},{"issue":"4","key":"2026040314032777300_ref057","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s00453-005-1177-7","article-title":"Simultaneous optimization via approximate ma jorization for concave profits or convex costs","volume":"44","author":"Goel","year":"2006","journal-title":"Algorithmica"},{"key":"2026040314032777300_ref058","first-page":"384","article-title":"Approximate ma jorization and fair online load balancing","author":"Goel","year":"2001","journal-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"1","key":"2026040314032777300_ref059","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1006\/jcss.2001.1755","article-title":"Combining fairness with throughput: online routing with multiple objectives","volume":"63","author":"Goel","year":"2001","journal-title":"Journal of Computer and System Science"},{"key":"2026040314032777300_ref060","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","article-title":"A general approximation technique for constrained forest problems","volume":"24","author":"Goemans","year":"1995","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"2026040314032777300_ref061","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","article-title":"Bounds for certain multiprocessing anomalies","volume":"45","author":"Graham","year":"1966","journal-title":"Bell System Technical Journal"},{"key":"2026040314032777300_ref062","author":"Hochbaum","journal-title":"Approximation Algorithms for NP-Hard Problems"},{"key":"2026040314032777300_ref063","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1137\/0404033","article-title":"Dynamic Steiner tree problem","volume":"4","author":"Imase","year":"1991","journal-title":"SIAM Journal Discrete Mathematics"},{"key":"2026040314032777300_ref064","article-title":"Competitive analysis of paging: A survey","author":"Irani","journal-title":"Proceedings of the Workshop on Online Algorithms"},{"key":"2026040314032777300_ref065","first-page":"701","article-title":"Page replacement with multi-size pages and applications to web caching","author":"Irani","year":"1997","journal-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing"},{"issue":"4","key":"2026040314032777300_ref066","doi-asserted-by":"crossref","first-page":"624","DOI":"10.1007\/s00453-001-0095-6","article-title":"Randomized weighted caching with two page weights","volume":"32","author":"Irani","year":"2002","journal-title":"Algorithmica"},{"issue":"7","key":"2026040314032777300_ref067","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1109\/TCOM.1981.1095081","article-title":"Bottleneck flow control","volume":"29","author":"Jaffe","year":"1981","journal-title":"IEEE Transactions on Communications"},{"key":"2026040314032777300_ref068","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","volume":"9","author":"Johnson","year":"1974","journal-title":"Journal of Computer and System Sciences"},{"issue":"233-1","key":"2026040314032777300_ref069","article-title":"An optimal deterministic algorithm for online b-matching","volume":"233","author":"Kalyanasundaram","journal-title":"Theoretical Computer Science"},{"key":"2026040314032777300_ref070","first-page":"502","article-title":"Dynamic TCP acknowledgement and other stories about e\/(e - 1)","author":"Karlin","year":"2001","journal-title":"Proceedings of the ACM Symposium on Theory of Computing"},{"issue":"6","key":"2026040314032777300_ref071","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/BF01189993","article-title":"Competitive randomized algorithms for nonuniform problems","volume":"11","author":"Karlin","year":"1994","journal-title":"Algorithmica"},{"key":"2026040314032777300_ref072","first-page":"244","article-title":"Competitive snoopy caching","author":"Karlin","year":"1986","journal-title":"Proceedings of the 27th Annual Symposium on Foundations of Computer Science"},{"key":"2026040314032777300_ref073","first-page":"352","article-title":"An optimal algorithm for online bipartite matching","author":"Karp","year":"1990","journal-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing"},{"key":"2026040314032777300_ref074","first-page":"568","article-title":"Fairness in routing and load balancing","author":"Kleinberg","journal-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science"},{"key":"2026040314032777300_ref075","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1109\/SFCS.2001.959928","article-title":"Tight approximation results for general covering integer programs","author":"Kolliopoulos","year":"2001","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"issue":"5","key":"2026040314032777300_ref076","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1145\/210118.210128","article-title":"On the k-server conjecture","volume":"42","author":"Koutsoupias","year":"1995","journal-title":"Journal of the ACM"},{"key":"2026040314032777300_ref077","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/SFCS.2000.892067","article-title":"Fairness measures for resource allocation","author":"Kumar","year":"2000","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314032777300_ref078","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","article-title":"On the ratio of optimal and fractional covers","volume":"13","author":"Lovasz","year":"1975","journal-title":"Discrete Mathematics"},{"key":"2026040314032777300_ref079","first-page":"448","article-title":"A parallel approximation algorithm for positive linear programming","author":"Luby","year":"1993","journal-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing"},{"key":"2026040314032777300_ref080","first-page":"243","article-title":"Multi-unit auctions with unknown supply","author":"Mahdian","year":"2006","journal-title":"Proceedings of the 7th ACM Conference on Electronic Commerce"},{"issue":"6","key":"2026040314032777300_ref081","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1007\/BF01759073","article-title":"A strongly competitive randomized paging algorithm","volume":"6","author":"McGeoch","year":"1991","journal-title":"Algorithmica"},{"issue":"5","key":"2026040314032777300_ref082","doi-asserted-by":"crossref","DOI":"10.1145\/1284320.1284321","article-title":"Adwords and generalized online matching","volume":"54","author":"Mehta","journal-title":"Journal of the ACM"},{"key":"2026040314032777300_ref083","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1109\/SFCS.2005.72","article-title":"The parking permit problem","author":"Meyerson","year":"2005","journal-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science"},{"key":"2026040314032777300_ref084","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","article-title":"Fast approximation algorithms for fractional packing and covering problems","volume":"20","author":"Plotkin","year":"1995","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"2026040314032777300_ref085","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","article-title":"Probabilistic construction of deterministic algorithms: Approximating packing integer programs","volume":"37","author":"Raghavan","year":"1988","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314032777300_ref086","article-title":"Randomized rounding: A technique for prov- ably good algorithms and algorithmic proofs","volume":"7","author":"Raghavan","journal-title":"Combinatorica"},{"key":"2026040314032777300_ref087","first-page":"86","article-title":"A general decomposition theorem for the k-server problem","author":"Seiden","year":"2001","journal-title":"Proceedings of the 9th Annual European Symposium on Algorithms"},{"issue":"2","key":"2026040314032777300_ref088","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","article-title":"Amortized efficiency of list update and paging rules","volume":"28","author":"Sleator","year":"1985","journal-title":"Communications of the ACM"},{"issue":"2","key":"2026040314032777300_ref089","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1137\/S0097539796314240","article-title":"Improved approximation guarantees for packing and covering integer programs","volume":"29","author":"Srinivasan","year":"1999","journal-title":"SIAM Journal on Computing"},{"key":"2026040314032777300_ref090","author":"Vazirani","journal-title":"Approximation Algorithms"},{"key":"2026040314032777300_ref091","first-page":"241","article-title":"On-line caching as cache size varies","author":"Young","year":"1991","journal-title":"SODA \u201991: Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"6","key":"2026040314032777300_ref092","first-page":"525","article-title":"The k-server dual and loose competitiveness for paging","volume":"11","author":"Young","year":"1994","journal-title":"Algo- rithmica"},{"key":"2026040314032777300_ref093","first-page":"170","article-title":"Randomized rounding without solving the linear program","author":"Young","year":"1995","journal-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"2026040314032777300_ref094","first-page":"82","article-title":"On-line file caching","author":"Young","year":"1998","journal-title":"Proceedings of the 9th Annual ACM- SIAM Symposium on Discrete Algorithms"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/3\/2-3\/93\/11156947\/0400000024en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/3\/2-3\/93\/11156947\/0400000024en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T18:03:51Z","timestamp":1775239431000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/3\/2-3\/93\/1332488\/The-Design-of-Competitive-Online-Algorithms-via-a"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,15]]},"references-count":94,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2009,5,15]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000024","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,15]]}}}