Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
From MaRDI portal
Publication:4598176
DOI10.4230/LIPIcs.ICALP.2016.39zbMath1388.68318arXiv1511.05886OpenAlexW2963432725MaRDI QIDQ4598176
Publication date: 19 December 2017
Full work available at URL: https://arxiv.org/abs/1511.05886
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (13)
On the advice complexity of the \(k\)-server problem ⋮ Improved analysis of the online set cover problem with advice ⋮ Parallel solutions for ordinal scheduling with a small number of machines ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ On the advice complexity of the online dominating set problem ⋮ Online algorithms with advice: the tape model ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Advice complexity of priority algorithms ⋮ Weighted online problems with advice ⋮ Online Minimum Spanning Tree with Advice ⋮ Online bin covering with advice ⋮ Weighted Online Problems with Advice ⋮ Online bin packing with advice of small size
This page was built for publication: Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
