New version on arXiv of an older paper: Algorithms for Wireless Capacity

We have recently posted the following paper on arXiv:

• Olga Goussevskaia, Magnus M. Halldorsson and Roger Wattenhofer: Algorithms for Wireless Capacity. http://arxiv.org/abs/1203.0536

This is a full and improved version of results that were given in two papers in 2009, in Infocom and then in ICALP.
   The main result is the first constant-factor approximation algorithm for the capacity problem with uniform power, as we call it; also known as maximum independent set of links and max single-shot link scheduling. This introduced a simple (but not trivial) greedy strategy that has been adapted to give effective algorithms for various variations and extensions (e.g. other power assignments in general metrics (SODA'11); power control (Kesselheim SODA'11)). It also shows that the model is robust to minor changes in the parameters.
  The Infocom paper currently has 79 citations on Google Scholar and the ICALP paper 45.