Combinatorial Online Planning

Many problems are naturally online problems. They require decisions to be made on the basis of incomplete data. In online optimization the input is modelled as a (finite) sequence of requests which are given step-by-step to an online algorithm. After a request becomes known, the online algorithm must make a decision without information about future requests. Depending on the specific problem, the decisions of the algorithm might be further constrained.

The goal of this project is to obtain new results for the construction and analysis of online algorithms. We want to overcome the weaknesses of competitive analysis (the "standard tool" for theoretical analysis of online algorithms), which is often overly pessimistic.