**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.This

objective is especially relevant to the field of routing optimization for humanitarian relief efforts, where

the focus is to send the relief quickly to everyone. 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

objective is especially popular in the field of humanitarian relief routing optimization, as the focus

there is to reach everyone quickly. 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.

## The Goal of this 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,

1such 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. We

would also be interested in obtaining better heuristics for the min-max problems, especially in the

context of humanitarian relief routing [4].

### 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. Opera- tions 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, March 2015. |

[3] | L. Kovács, A. Agárdi, T. Bányai, Fitness Landscape Analysis and Edge Weighting-Based Opti- mization of Vehicle Routing Problems. Processes, vol. 8, 1363, 2020 |

[4] | Campbell, Ann Melissa, Dieter Vandenbussche, and William Hermann. "Routing for relief efforts." Transportation science 42.2 (2008): 127-145. |

# Project Team

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

**Supervisor**

Chair for Algorithm Engineering

Hasso Plattner Institute

Office: K-2.15

E-Mail: Friedrich(at)hpi.de

## Dr. Davis Issac

**Advisor**

Hasso Plattner Institute

Office: K-2.07

Tel.: +49 331 5509-4841

E-Mail: Davis.Issac(at)hpi.de

## Dr. Nikhil Kumar

**Advisor**

Hasso Plattner Institute

Office: K-2.07

Phone: +49 331 5509-3400

Email: Nikhil.Kumar (at) hpi.de