Ph.D Thesis

Ph.D StudentFarbstein Boaz
SubjectApproximation Algorithms for Routing Problems
DepartmentDepartment of Industrial Engineering and Management
Supervisor ASSOCIATE PROF. Asaf Levin
Full Thesis textFull thesis text - English Version


We consider three different routing problems on a graph. In all the problems, there are rewards on the nodes of the graph and there is a length function associated with the edges of the graph. The objective is to find a path (or paths) that maximizes the total reward collected from nodes traversed by it. The length of the prefix of the path until each node influences (differently in each problem) the reward collected from that node. For each problem we introduce an approximation algorithm that improves the best-known approximation ratio for the problem. The first problem is the Discounted Reward TSP where the reward of each node deteriorates exponentially in time. That is, the larger the prefix of the path until a node is, the smaller the reward that is collected from it. In the second problem, Multiple Depot VRP with Budget Constraints (DVB), there exists an upper bound on the lengths of the paths that collect rewards from the nodes of the graph. In the algorithm for DVB we use, as a black box, a greedy approximation algorithm for Maximum Coverage with Group Budget Constrains (MCG), where we improve the analysis of the known greedy algorithm to receive a better approximation ratio for MCG. In the third problem, Deadline TSP, each node has a deadline such that a path collects its reward as long as it visits the node by its deadline.