|M.Sc Student||Farbstein Boaz|
|Subject||Min-Max Cover of a Graph with a Constant Number of Parts|
|Department||Department of Industrial Engineering and Management||Supervisor||ASSOCIATE PROF. Asaf Levin|
|Full Thesis text|
We consider a variety of vehicle routing problems. The input consists of a graph and edge lengths. Customers located at the vertices have to be visited by a set of vehicles. Two important parameters are k the number of vehicles, and the longest distance traveled by a vehicle denoted by λ. Here, we consider k to be a given bound on the maximum number of vehicles, and thus the decision maker cannot increase its value. Therefore, the goal will be to minimize λ. We study different variations of this problem, where for instance instead of servicing the customers using paths, we can serve them using spanning trees or stars. For all these variations, we present new approximation algorithms with FPT time (where k is the parameter) which improve the known approximation guarantees for these problems.