Some Results in Universal and A Priori Optimization
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
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
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.