Some Results in Universal and A Priori Optimization
In this thesis, some combinatorial problems are studied in the light of the a priori and universal optimization framework, as introduced for the Traveling Salesman Problem by Jaillet, and by Bartholdi & Platzman, respectively. In both the a priori, as well as the universal framework, there is an underlying optimization problem, and (advance) knowledge of the potential instances that can arise. The goal is to find a "master solution" of a special form, that in turn fully specifies the solution to any potential instance of the optimization problem that arises. In the case of the traveling salesman problem, the master solution is a tour on the complete set of all customers in the potential instances. This master tour now specifies the solution for each instance as follows: the customers in the instance will be visited in the same order as the master solution. The results of this thesis include an optimization algorithm for the a priori and universal Traveling Salesman Problem on tree metrics, an $O(\log n)$-approximation algorithm for the a priori Traveling Salesman Problem, with no restrictions on the metric space and no knowledge about the probability distribution on the potential instances, an approximation algorithm for a priori and universal $1\,|\,pmtn, r_j\,|\,\sum C_j$, and a nearly optimal algorithm for AdWords. We also study the real life problem of creating Nearly Isogenic Lines (NILs). The solution that we propose can be seen as an a priori solution, since the solution that we propose is nonadaptive. Finally, in addition to dealing with a priori and universal optimization, we also give a Fully Polynomial Time Approximation Scheme (FPTAS) for a certain Stochastic Dynamic Programs, with an application in option pricing.
universal optimization; a priori optimization; approximation algorithms; stochastic dynamic programming; option pricing; traveling salesman problem; nearly isogenic lines; approximate dynamic programming; scheduling