Speaker: Sixia Chen
Day:  Wednesday, 11/14/2007
Room: ITEB 336
Time: 2:00-3:00pm

Titile: Complexity and Approximation algorithm of two problems in Geometric
SINR
 
Abstract: In this talk, we study two problems of scheduling wireless links
in the geometric SINR model, which explicitly uses the fact that nodes are
distributed in the Euclidean plane. First we prove that the two problems to
be NP-complete: Scheduling and One-Shot Scheduling. The first problem
consists in finding a minimum-length schedule for a given set of links. The
second problem receives a weighted set of links as input and consists in
finding a maximum-weight subset of links to be scheduled simutaneously in
one shot. In addition to the complexity proofs, we will also discuss an
approximation algorithm for each problem.
 
Reference: Complexity in Geometric SINR, O.Goussevskaia, Y.A.Oswald,
R.Wattenhofer, MobiHoc'07