A Primal-Dual Randomized Algorithm for Weighted Paging
From MaRDI portal
Publication:5395689
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
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