Multi-Objective Online Optimization

In online optimization, an algorithm has to make decisions based on a sequence of incoming bits of information without knowledge of future inputs. The performance of an online algorithms is commonly evaluated by comparing its objective value to the optimal offline solution, also referred to as competitive analysis. Thus far, the notion of online algorithms and competitive analysis is only known for single-objective optimization problems. We transfer the concept to multiple objectives and introduce competitive analysis for multi-objective optimization problems. Due to the shift from a single optimal solution in single-objective optimization to a set of efficient solutions in multi-objective optimization, the transformation of the concept of competitive analysis to multiple objectives is not straightforward. In this talk, the novel definition of multi-objective online optimization is discussed and substantiated by the analysis of multi-objective counterparts of classical online optimization problems.