A Primal-Dual Randomized Algorithm for Weighted Paging

DOI10.1145/2339123.2339126zbMath1281.68238OpenAlexW2033156334MaRDI QIDQ5395689

Joseph (Seffi) Naor, Nikhil Bansal, Niv Buchbinder

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2339123.2339126

zbMATH Keywords

randomizationonline algorithmsprimal-dualweighted paging

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (21)

Caching with Time Windows and Delays ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Primal-dual analysis for online interval scheduling problems ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Unnamed Item ⋮ The \(k\)-server problem ⋮ Frequency capping in online advertising ⋮ On Variants of File Caching ⋮ The k-Server Problem with Delays on the Uniform Metric Space ⋮ The \(k\)-resource problem in uniform metric spaces ⋮ Metrical service systems with multiple servers ⋮ Approximating Sparse Covering Integer Programs Online ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems ⋮ Stochastic dominance and the bijective ratio of online algorithms ⋮ Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing ⋮ Incentive compatible mulit-unit combinatorial auctions: a primal dual approach ⋮ Online file caching with rejection penalties ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

This page was built for publication: A Primal-Dual Randomized Algorithm for Weighted Paging