On complexity reduction of the LP bound computation and related problems
Files
(Published version)
Date
2011
Authors
Thakor, S.
Grant, A.
Chan, T.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the international symposium on network coding, NETCOD 2011, 2011, iss.5978922, pp.1-6
Statement of Responsibility
Conference Name
2011 International symposium on network coding, NETCOD 2011 (25 Jul 2011 - 27 Jul 2011 : China)
Abstract
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2011 IEEE
Access Condition Notes: Accepted manuscript is available open access