טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentFarbstein Boaz
SubjectMin-Max Cover of a Graph with a Constant Number of Parts
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Asaf Levin
Full Thesis textFull thesis text - English Version


Abstract

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.