WorksComputer Science
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than
Abstract
A well-known conjecture in online algorithms is that the (randomized) competitive ratio of online budgeted allocation is . We refute this conjecture and show that every randomized online algorithm has competitive ratio at most for a (small) absolute constant .