Advice Complexity and Barely Random Algorithms
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 algorithms...