On optimizing multi-sequence functionals for competitive analysis.
Tom Kamphans, Elmar Langetepe · 2005
The efficiency of an online motion planning algorithm often is measured by a constant competitive factor C. Competitivity means, that the cost of an C-competitive online strategy with incomplete information is only C times worse than the optimal offline solution with full information. If a strategy is represented by an infinite sequence X = f1,f2,...,the problem of finding a strategy with minimal C often results in minimizing functionals Fk in X. There are two main paradigm for finding an optimal sequence f1,f2,... that minimizes Fk for all k. Namely, optimality of the exponential function and equality approach. If the strategy has to be defined by more than one interacting sequence both approaches may fail. We show a simple motion planning example with two interacting sequences and present its solution. 1