Maximum weighted matching with interference constraints

In this paper, we study the problem of utility maximization in multi-hop wireless systems. To study the effect of wireless interference constraints on the utility maximization problem, we introduce a new class of weighted matching problems, namely Maximum Weighted K-Valid Matching problems (MWKVMPs). For K = 1, MWKVMP corresponds to the well studied Maximum Weighted Matching problem (MWMP) in the literature, which can be solved in polynomial time. We prove several interesting results concerning the hardness of these problems for K >= 2. In particular, we show that MWKVMP does not even belong to APX; where APX denotes the class of problems to which a constant factor approximation can be obtained in polynomial time. Our results have strong implications concerning the hardness of scheduling transmissions in multi-hop wireless systems.