Some Results in Universal and A Priori Optimization

Other Titles


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(logn)-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,rj|∑Cj, 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.

Journal / Series

Volume & Issue



Date Issued




universal optimization; a priori optimization; approximation algorithms; stochastic dynamic programming; option pricing; traveling salesman problem; nearly isogenic lines; approximate dynamic programming; scheduling


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

bibid: 6475893

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record