Prof. Dr. Tobias Friedrich

Covering Graphs Using Simpler Structures and Vehicle Routing Problems

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. 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 problem will be the focus of our project. Since this problem is NP-Hard, our main focus will be on designing efficient approximation algorithms.

Goal of the Project

In this project, we plan to study the following problems from the view point of approximation algorithms. Rooted Min-Max Tree Cover (RMMTC): We are given an undirected graph G with non-negative edge lengths, a pre-specified multiset of root vertices R and a positive integer k. We wish to find a set of k sub-trees of G, each containing a unique vertex from R, such that every vertex of G is contained in at least one of these k trees. The objective is to minimize the maximum cost among all the trees.

This problem generalises the Minimum Makespan Scheduling and is already NP-Hard when G is a star and |R|=1. Even et al. [1] gave a 4-approximation algorithm for RMMTC and it has not been improved since. There have been improvements in the approximation ratio for some special cases, but the general problem still remains open. The goal of the project is to improve upon this approximation factor. We will begin by looking at the special case when R is a singleton. We already have preliminary ideas on improving the approximation guarantee in this case and hope to improve the approximation ratio further by pushing these ideas and coming up with new ones.

We will also study a closely related problem, called the Rooted Min Max Tour Cover, where instead of trees we wish to find closed walks starting and ending at r. There are many other closely related variants of this problem as well  (see [2]) and we hope that the ideas developed in the context of RMMTC will be useful in developing improved approximation algorithms for these as well. We also plan to evaluate the performance of the proposed algorithms through experimental simulations.

What we expect from you.

An aptitude for doing theoretical research in a relevant topic of Graph Theory. Curiosity to investigate the existing models and creativity to extend the current framework. Some basic coding skills to complement theoretical results with experiments.

What you can expect from us.

We will gently introduce you to the field and accompany you all along this interesting journey. If circumstances permit, our weekly meeting will be in person, otherwise via Zoom.  This will be a team effort, and we aim at publishing our results at a renowned international conference.

 [1] G. Even, N. Garg, J. Könemann, R. Ravi and A. Sinha. Min-Max Tree Covers of Graphs. Operations Research Letters, 32(4):309–315, 2004. [2] W. Xu, W. Liang and X. Lin, Approximation Algorithms for Min-Max Cycle Cover Problems, in IEEE Transactions on Computers, vol. 64, no. 3, pp. 600-613, 2015. [3] L. Kovács, A. Agárdi, T. Bányai, Fitness Landscape Analysis and Edge Weighting-Based Optimization of Vehicle Routing Problems. Processes, vol. 8, 1363, 2020.

Project Team

The Master Project is organized by the Algorithm Engineering Group. The following group members are participating:

Prof. Dr. Tobias Friedrich

Supervisor

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: A-1.10
E-Mail: Friedrich(at)hpi.de

Dr. Davis Issac

Supervisor

Hasso Plattner Institute

Office: A-1.11
Tel.: +49 331 5509-4841
E-Mail: Davis.Issac(at)hpi.de

Dr. Nikhil Kumar

Supervisor

Hasso Plattner Institute

Office: A-1.11

Phone: +49 331 5509-3400

Email: Nikhil.Kumar (at) hpi.de