TY  - THES
T1  - Online algorithms for conversion problems : an approach to conjoin worst-case analysis and empirical-case analysis
A1  - Mohr,Esther
Y1  - 2011/10/27
N2  - A conversion problem deals with the scenario of converting an asset into another asset and possibly back. This work considers financial assets and investigates online algorithms to perform the conversion. When analyzing the performance of online conversion algorithms, as yet the common approach is to analyze heuristic conversion algorithms from an experimental perspective, and to analyze guaranteeing conversion algorithms from an analytical perspective. This work conjoins these two approaches in order to verify an algorithms' applicability to practical problems. We focus on the analysis of preemptive and non-preemptive online conversion problems from the literature. We derive both, empirical-case as well as worst-case results. Competitive analysis is done by considering worst-case scenarios. First, the question whether the applicability of heuristic conversion algorithms can be verified through competitive analysis is to be answered. The competitive ratio of selected heuristic algorithms is derived using competitive analysis. Second, the question whether the applicability of guaranteeing conversion algorithms can be verified through experiments is to be answered. Empirical-case results of selected guaranteeing algorithms are derived using exploratory data analysis. Backtesting is done assuming uncertainty about asset prices, and the results are analyzed statistically. Empirical-case analysis quantifies the return to be expected based on historical data. In contrast, the worst-case competitive analysis approach minimizes the maximum regret based on worst-case scenarios. Hence the results, presented in the form of research papers, show that combining this optimistic view with this pessimistic view provides an insight into the applicability of online conversion algorithms to practical problems. The work concludes giving directions for future work.
KW  - Online Algorithmen
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/4364
ER  -