Maximizing network capacity of MPR-capable wireless networks

Multi-packet reception (MPR) technology provides a means of boosting wireless network capacity without requiring additional spectrum. It has received widespread attention over the past two decades from both industry and academic researchers. Despite the huge promise and considerable attention, provable good algorithms for maximizing network capacity in MPR-capable wireless networks are missing in the state of the art. One major technical obstacle is due to the complicated non-binary nature of the link independence; something which appears intractable with existing graph-theoretic methods. In this paper, we present practical polynomial-time approximation algorithms for variants of capacity optimization problems in MPR-capable wireless networks which achieve constant approximation bounds for the first time ever. In addition, polynomial-time approximation schemes are developed for those variants in wireless networks with constant-bounded MPR capabilities.