Dept of CS Seminar Approximation algorithms for relay placement 8/14

August 13, 2009 at 10:14 am (Uncategorized)

Title:   Approximation algorithms for relay placement
Speaker: Sandor Fekete, Braunschweig University of Technology, Germany

Date: Friday, August 14, 2009
Time: 11:00 – 12:00
Location: Engineering and Computer Science Building (ECS), Room # 660

In the relay placement problem the input is a set of sensors (given
by a set of points in the plane) and a number r>=1, the communication
range of a relay.  In the one-tier version of the problem the objective
is to place a minimum number of relays so that between every pair of
sensors there is a path through sensors and/or relays, such that the
consecutive vertices of the path are within distance r if both vertices
are relays and within distance 1 otherwise. The two-tier version adds
the restrictions that the path must go through relays, and not through
sensors.  We present a 3.11-approximation algorithm for the one-tier
version and a PTAS for the two-tier version.  We also show that the
one-tier version admits no PTAS, assuming P!=NP.


Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: