Motivation
Covering vertices of a given graph using simpler structures, for example, paths, trees,
stars and so on, have long attracted the attention of the Computer Science and Operations Research
communities. This can be attributed to a variety of applications in vehicle routing, network design
and related problems. One classical example is the so-called ‘Nurse Location Problem’ [1]. The goal
is to place a group of nurses at different locations and find a tour for each of them so that every
patient is visited by a nurse. A similar setting arises in vehicle routing. Suppose we are given a set of
vehicles, initially located at a given set of depots. The goal is to find a tour for each of these vehicles,
each starting and ending at the respective depots to cover client demands at various locations.This
objective is especially relevant to the field of routing optimization for humanitarian relief efforts, where
the focus is to send the relief quickly to everyone. One of the most popular objectives is to minimize
the maximum distance travelled by any vehicle, also known as the make span of the solution. This
objective is especially popular in the field of humanitarian relief routing optimization, as the focus
there is to reach everyone quickly. This problem will be the focus of our project. Since this problem
is NP-Hard, our main focus will be on designing efficient approximation algorithms.