Online Optimization with Uncertain Information
Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi · ACM Transactions on Algorithms · 2012
We introduce a new framework for designing online algorithms that can incorporate additional information about the input sequence, while maintaining a reasonable competitive ratio if the additional information is incorrect. Within this framework, we present online algorithms for several problems including allocation of online advertisement space, load balancing, and facility location.