Randomized Competitive Algorithms for Generalized Caching

DOI10.1137/090779000zbMath1252.68355OpenAlexW2905904719MaRDI QIDQ2903523

Nikhil Bansal, Joseph (Seffi) Naor

Publication date: 10 August 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/a8df0355-2a4b-42e4-9232-931cbb6bc4c9

zbMATH Keywords

online algorithmsfault modelgeneralized caching problembit modelonline primal-dual framework

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Related Items (9)

General caching is hard: even with small pages ⋮ Online covering with \(\ell_q\)-norm objectives and applications to network design ⋮ Unnamed Item ⋮ Frequency capping in online advertising ⋮ Approximating Sparse Covering Integer Programs Online ⋮ Unnamed Item ⋮ Facility Location with Matroid or Knapsack Constraints ⋮ Incentive compatible mulit-unit combinatorial auctions: a primal dual approach ⋮ Online file caching with rejection penalties

This page was built for publication: Randomized Competitive Algorithms for Generalized Caching