Approximation Algorithms for some Min-max Vehicle Routing Problems

Vehicle routing problems are optimization problems that deal with the location and routing of vehicles. A set of clients based in different locations need to be served by a fleet of vehicles. The clients and vehicle depots are modeled as being placed on the vertices of a graph and the distances between them as a metric. Thus, a solution to a vehicle routing problem corresponds to covering the graph using a number of subgraphs, each denoting the route of a vehicle. In this thesis, we consider min-max vehicle routing problems, in which the maximum cost incurred by the subgraph corresponding to each vehicle is to be minimized. We study two types of covering problems and present new or improved approximation algorithms for them.;In Chapter 3, we study the unrooted min-max k-star cover problem. Given a metric (V, c) and a number k, a set of stars S1,...,Sk in G is called a k-star cover, if they cover all the vertices of G, i.e. V = ∪ki=1 V (Si). The rooted min-max k-star cover problem is that of giving a k-star cover of G where the maximum cost of a star under the metric c is minimized. We improve on the approximation ratio when the number of stars k is slightly violated, i.e. bi-criteria approximations and present an (O(1/epsilon), 1 + epsilon) bi-criteria approximation. We also study the problem on more restricted metrics, namely the line metric and Euclidean metric. For the problem on the line metric, we present a QPTAS, and for the problem on the line metric in the special case that the stars are non-crossing, we present a PTAS for the unrooted min-max k-star cover problem. Then, we explore the possibility of Polynomial time approximation schemes on the Euclidean metric. We rule out this possibility by giving an APX-hardness reduction.;In Chapter 2, we study the rooted and unrooted variants of min-max k-tour cover problem. Given a metric (V, c) and a number k, a set of tours T1 ,..., Tk in G is called a k-tour cover, if they cover all the vertices of G, i.e. V = ∪ki=1 V ( Ti ). The unrooted min-max k-tour cover problem is that of giving a k-tour cover of G where the maximum cost of a tour under the metric c is minimized. Analogously, in the rooted version, we are given a subset of vertices R of size k and each tour of the k-tour cover is required to be rooted at a distinct vertex in R. We improve on the approximation ratios of these problems by giving a (16=3 + epsilon)-approximation algorithm for the unrooted min-max k-tour cover problem and a (7 + epsilon)-approximation algorithm for rooted version.