Online Algorithms for Conversion Problems

Online conversion algorithms are broadly of two types - heuristic conversion algorithms and guaranteeing conversion algorithms. The analysis of heuristic conversion algorithms is based on an experimental perspective, whereas guaranteeing conversion algorithms are analyzed from an analytical perspective. This work conjoins these two approaches in order to verify an algorithms’ applicability to practical problems. Empirical-case as well as worst-case results are derived. First, the question whether the applicability of heuristic conversion algorithms can be verified through competitive analysis is to be answered. Second, the question whether the applicability of guaranteeing conversion algorithms can be verified through experiments is to be answered. Results, presented in the form of research papers, show that combining these approaches provides an insight into the applicability of online conversion algorithms to practical problems