This paper studies maximum multicommodity flow and maximum concurrent flow in multihop wireless networks subject to both bandwidth and interference constraints. The existing proof of the NP-hardness of both problems is too contrived to be applicable to meaningful multihop wireless networks. In addition, all known constant-approximation algorithms for both problems restricted to various network classes are super-exponential in running time. Some of them are simply incorrect. In this paper, we first provide a rigorous proof of the NP-hardness of both problems even in very simple settings. Then, we show that both problems restricted to a broad family of multihop wireless networks admit polynomial-time approximation scheme (PTAS). After that, we develop a unified framework for the design and analysis of polynomial approximation algorithms for both problems. Following such framework, we obtain polynomial constant-approximation algorithms for both problems restricted to a broad network family. The approximation ratios of these algorithms are also better than those known in the literature.
Journal name not available for this finding