Approximation algorithms for sequencing problems.

摘要

This thesis presents approximation algorithms for some sequencing problems, with an emphasis on vehicle routing. Vehicle Routing Problems (VRPs) form a rich class of variants of the basic Traveling Salesman Problem, that are also practically motivated. The VRPs considered in this thesis include single and multiple vehicle Dial a Ride, VRP with Stochastic Demands, Directed Orienteering and Directed Minimum Latency. Other sequencing problems studied in this thesis are Permutation Flowshop Scheduling and Maximum Quadratic Assignment.