On Complexity Reduction of the LP Bound Computation and Related Problems
Computing the LP bound for network coding capacity and proving a basic information inequality are linear optimization problems. The number of dimensions and constraints of the problems increase exponentially with the number of random variables involved. In the first instance, producing constraints with exponential size exhausts computational memory resources as the number of random variables increases. Secondly, the well known simplex algorithm for solving linear programming problems has exponential worst case complexity in the problem size, making it doubly exponential in the number of random variables. In this correspondence, we focus on generating a set of constraints with significantly reduced size and yet characterizing the same feasible region for these optimization problems. As a result, it is now possible to produce constraint sets for problems with larger number of random variables which was practically impossible due to limited memory resources. Moreover, reduction in problem size also means solving the problems faster.
Satyajit Thakor Alex Grant Terence Chan
Institute for Telecommunications Research University of South Australia
国际会议
2011 International Symposium on Network Coding(2011网络编码国际会议 NETCOD 2011)
北京
英文
1-6
2011-07-25（万方平台首次上网日期，不代表论文的发表时间）