Modified bipartite matching for multiobjective optimization: Application to antenna assignments in MIMO systems

Abstract

Based on the Hungarian algorithm, the Kuhn-Munkres algorithm can provide the maximum weight bipartite matching for assignment problems. However, it can only solve the single objective optimization problem. In this paper, we formulate the multi-objective optimization (MO) problem for bipartite matching, and propose a modified bipartite matching (MBM) algorithm to approach the Pareto set with a low computational complexity and to dynamically select proper solutions with given constraints among the reduced matching set. In addition, our MBM algorithm is extended to the case of asymmetric bipartite graphs. Finally, we illustrate the application of MBM to antenna assignments in wireless multiple-input multiple-output (MIMO) systems for both symmetric and asymmetric scenarios, where we consider the multi-objective optimization problem with the maximization of the system capacity, total traffic priority, and long-term fairness among all mobile users. The simulation results show that MBM can effectively reduce the matching set and dynamically provide the optimized performance with different quality of service (QoS) requirements. © 2006 IEEE.