Speaker: Mike Dinitz

Title: Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model: Complexity and Game Theory

Abstract:
In this talk we consider the problem of maximizing the number of
supported connections in arbitrary wireless networks where a
transmission is supported if and only if the
signal-to-interference-plus-noise ratio at the receiver is greater
than some threshold. The aim is to choose transmission powers for each
connection so as to maximize the number of connections for which this
threshold is met.

We believe that analyzing this problem is important both in its own
right and also because it arises as a subproblem in many other areas
of wireless networking. We study both the complexity of the problem
and also present some game theoretic results regarding capacity that
is achieved by completely distributed algorithms. We also feel that
this problem is intriguing since it involves both continuous aspects
(i.e. choosing the transmission powers) as well as discrete aspects
(i.e. which connections should be supported).  Time permitting, we
will discuss the following results:

1) We show that maximizing the number of supported connections is
NP-hard, even when there is no background noise.  This is in contrast
to the problem of determining whether or not a given set of
connections is feasible since that problem can be solved via linear
programming.

2) We give an approximation algorithm that runs in polynomial time and
has an approximation ratio that is independent of the number of
connections.

3) We examine a completely distributed algorithm and analyze it as a
game in which a connection receives a positive payoff if it is
successful and a negative payoff if it is unsuccessful while
transmitting with nonzero power.  We show that in this game the price
of anarchy is independent of the number of connections.

This is joint work with Matthew Andrews.