Time: 2:00pm Tuesday, 19th May.
Location: SIT 459
Speaker: Tim van Lieshout, TU Eindhoven
Title: New results on feed link placement
Given a polygon representing a part of a network and some point p in its interior, the task is to extend the network by connecting p to the boundary of the polygon such that the detour from p to every point on the boundary of the polygon is minimised.
Our main focus is on minimising the average detour and on placing k>0 feed links. We first show a linear time algorithm that adds one edge from p to P such that the average detour is minimised. As well as a variation of this algorithm that places k feed links optimally to minimise the average detour. Finally we show a fast (1+\eps)-approximation for placing k feed links while minimizing the average detour.