Conference proceeding
Exploiting symmetry in computing polyhedral bounds on network coding rate regions
The Institute of Electrical and Electronics Engineers, Inc. (IEEE) Conference Proceedings
01 Jun 2015
Abstract
Conference Title: 2015 International Symposium on Network Coding (NetCod) Conference Start Date: 2015, June 22 Conference End Date: 2015, June 24 Conference Location: Sydney, Australia We propose an algorithm for computing polyhedral bounds on the rate regions of multi-source multi-sink network coding instances given the knowledge of symmetries of the instance as captured by the network symmetry group. We show how the network symmetry group can be interpreted as a group of symmetries of a polyhedron, which in turn enables the use techniques for exploiting symmetry in polyhedral computation to reduce the complexity of calculating the rate region. We apply these techniques to the polyhedral projection algorithm chm to list only those facets and extreme points of a polyhedral bound on rate region that are inequivalent under the action of the network symmetry group. Additionally, a generalization of this algorithm that can exploit richer super-groups of polyhedral symmetries, the restricted affine symmetry groups, is discussed.
Metrics
6 Record Views
Details
- Title
- Exploiting symmetry in computing polyhedral bounds on network coding rate regions
- Creators
- Jayant ApteJohn Maclaren Walsh
- Publication Details
- The Institute of Electrical and Electronics Engineers, Inc. (IEEE) Conference Proceedings
- Publisher
- The Institute of Electrical and Electronics Engineers, Inc. (IEEE)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Identifiers
- 991019170146404721