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.