Research on the Optimization Problems in Network Coding
网络编码中的优化问题研究

This paper briefly reviews the theoretical researches on network coding, from which the significance of research on optimization problems is revealed. Based on the network information flow model, it makes a survey on the formulation, characteristics and algorithms of optimization problems with the latest results. According to the goal of optimization, the typical optimization problems in network coding are classified into four categories: minimum-cost multicast, throughput maximization in undirected networks, minimum number of coding nodes and links, topology design of network coding-based multicast networks. The general approaches to deal with these problems are categorized. For (linear or convex) programming problems, the solutions are summarized; for NP complete problems, the latest heuristic algorithms and their difficulties are analyzed. The perspectives on future work are also discussed.