you're reading...

SACT Seminar: New results on feed link placement

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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: