Computing bounds on network capacity regions as a polytope reconstruction problem
We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, boundedness and convexity when the finite field is fixed. We show that the network routing capacity region is a com...
| Egile Nagusiak: | , |
|---|---|
| Beste egile batzuk: | |
| Formatua: | Artikulua |
| Hizkuntza: | en_US |
| Argitaratua: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Sarrera elektronikoa: | http://hdl.handle.net/1721.1/73691 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826190957043777536 |
|---|---|
| author | Kim, Anthony Medard, Muriel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kim, Anthony Medard, Muriel |
| author_sort | Kim, Anthony |
| collection | MIT |
| description | We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, boundedness and convexity when the finite field is fixed. We show that the network routing capacity region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. We define the semi-network linear coding capacity region, with respect to a fixed finite field, that inner bounds the corresponding network linear coding capacity region, show that it is a computable rational polytope, and provide exact algorithms and approximation heuristics. We show connections between computing these regions and a polytope reconstruction problem and some combinatorial optimization problems, such as the minimum cost directed Steiner tree problem. We provide an example to illustrate our results. The algorithms are not necessarily polynomial-time. |
| first_indexed | 2024-09-23T08:47:55Z |
| format | Article |
| id | mit-1721.1/73691 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:47:55Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/736912022-09-30T11:18:46Z Computing bounds on network capacity regions as a polytope reconstruction problem Kim, Anthony Medard, Muriel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Medard, Muriel We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, boundedness and convexity when the finite field is fixed. We show that the network routing capacity region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. We define the semi-network linear coding capacity region, with respect to a fixed finite field, that inner bounds the corresponding network linear coding capacity region, show that it is a computable rational polytope, and provide exact algorithms and approximation heuristics. We show connections between computing these regions and a polytope reconstruction problem and some combinatorial optimization problems, such as the minimum cost directed Steiner tree problem. We provide an example to illustrate our results. The algorithms are not necessarily polynomial-time. 2012-10-10T13:12:19Z 2012-10-10T13:12:19Z 2011-10 2011-07 Article http://purl.org/eprint/type/ConferencePaper 978-1-4577-0594-6 978-1-4577-0596-0 2157-8095 http://hdl.handle.net/1721.1/73691 Kim, Anthony, and Muriel Medard. “Computing Bounds on Network Capacity Regions as a Polytope Reconstruction Problem.” IEEE International Symposium on Information Theory Proceedings (ISIT), 2011. 588–592. https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/ISIT.2011.6034197 Proceedings on the IEEE International Symposium on Information Theory Proceedings (ISIT), 2011 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Kim, Anthony Medard, Muriel Computing bounds on network capacity regions as a polytope reconstruction problem |
| title | Computing bounds on network capacity regions as a polytope reconstruction problem |
| title_full | Computing bounds on network capacity regions as a polytope reconstruction problem |
| title_fullStr | Computing bounds on network capacity regions as a polytope reconstruction problem |
| title_full_unstemmed | Computing bounds on network capacity regions as a polytope reconstruction problem |
| title_short | Computing bounds on network capacity regions as a polytope reconstruction problem |
| title_sort | computing bounds on network capacity regions as a polytope reconstruction problem |
| url | http://hdl.handle.net/1721.1/73691 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT kimanthony computingboundsonnetworkcapacityregionsasapolytopereconstructionproblem AT medardmuriel computingboundsonnetworkcapacityregionsasapolytopereconstructionproblem |