Advice Complexity and Barely Random Algorithms
Dennis Komm, Richard Královič (2011)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Recently, a new measurement – the – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, , and the problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our special focus goes to barely random algorithms, , randomized...