Deterministic network information flows using polylinking systems
Motivated by the deterministic wireless information flow model introduced by Avestimehr, Diggavi and Tse, we introduce a deterministic flow model based on combining polylinking systems, a notion introduced by Schrijver and closely related to polymatroids. Given is a set of vertices that can be parti...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/80851 https://orcid.org/0000-0002-0520-1165 |
| _version_ | 1811094784159252480 |
|---|---|
| author | Goemans, Michel X. Iwata, Satoru Zenklusen, Rico |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Iwata, Satoru Zenklusen, Rico |
| author_sort | Goemans, Michel X. |
| collection | MIT |
| description | Motivated by the deterministic wireless information flow model introduced by Avestimehr, Diggavi and Tse, we introduce a deterministic flow model based on combining polylinking systems, a notion introduced by Schrijver and closely related to polymatroids. Given is a set of vertices that can be partitioned into layers V[subscript 1],..., V[subscript r] and flow is sent across consecutive layers. There is no notion of edges, and how flow can be sent from one layer to the next is described by polylinking systems. Thanks to the abstract nature of polylinking systems, this new model is very general and gives large freedom in specifying how flow can be sent through the network. In particular, the new model includes the classical flow model of Ford and Fulkerson restricted to acyclic graphs as well as a wireless information flow model introduced by Avestimehr, Diggavi and Tse to approximate the Shannon capacity of Gaussian relay networks. In the framework of this ADT model, we can aggregate all vertices within a relay, and obtain a more compact and natural formulation of this model based on our polylinking flow model. This has also the advantage of allowing for non-integral capacities and flows. |
| first_indexed | 2024-09-23T16:05:03Z |
| format | Article |
| id | mit-1721.1/80851 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:05:03Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/808512022-09-29T18:08:23Z Deterministic network information flows using polylinking systems Goemans, Michel X. Iwata, Satoru Zenklusen, Rico Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Zenklusen, Rico Motivated by the deterministic wireless information flow model introduced by Avestimehr, Diggavi and Tse, we introduce a deterministic flow model based on combining polylinking systems, a notion introduced by Schrijver and closely related to polymatroids. Given is a set of vertices that can be partitioned into layers V[subscript 1],..., V[subscript r] and flow is sent across consecutive layers. There is no notion of edges, and how flow can be sent from one layer to the next is described by polylinking systems. Thanks to the abstract nature of polylinking systems, this new model is very general and gives large freedom in specifying how flow can be sent through the network. In particular, the new model includes the classical flow model of Ford and Fulkerson restricted to acyclic graphs as well as a wireless information flow model introduced by Avestimehr, Diggavi and Tse to approximate the Shannon capacity of Gaussian relay networks. In the framework of this ADT model, we can aggregate all vertices within a relay, and obtain a more compact and natural formulation of this model based on our polylinking flow model. This has also the advantage of allowing for non-integral capacities and flows. National Science Foundation (U.S.) (Contract CCF-0829878) United States. Office of Naval Research (Grant N00014-05-1-0148) 2013-09-23T13:34:16Z 2013-09-23T13:34:16Z 2010-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-6372-5 http://hdl.handle.net/1721.1/80851 Goemans, Michel X., Satoru Iwata, and Rico Zenklusen. “Deterministic network information flows using polylinking systems.” In IEEE Information Theory Workshop 2010 (ITW 2010), 1-1. Institute of Electrical and Electronics Engineers, 2010. © 2010 IEEE https://orcid.org/0000-0002-0520-1165 en_US http://dx.doi.org/10.1109/ITWKSPS.2010.5503218 Proceedings of the IEEE Information Theory Workshop 2010 (ITW 2010) Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Goemans, Michel X. Iwata, Satoru Zenklusen, Rico Deterministic network information flows using polylinking systems |
| title | Deterministic network information flows using polylinking systems |
| title_full | Deterministic network information flows using polylinking systems |
| title_fullStr | Deterministic network information flows using polylinking systems |
| title_full_unstemmed | Deterministic network information flows using polylinking systems |
| title_short | Deterministic network information flows using polylinking systems |
| title_sort | deterministic network information flows using polylinking systems |
| url | http://hdl.handle.net/1721.1/80851 https://orcid.org/0000-0002-0520-1165 |
| work_keys_str_mv | AT goemansmichelx deterministicnetworkinformationflowsusingpolylinkingsystems AT iwatasatoru deterministicnetworkinformationflowsusingpolylinkingsystems AT zenklusenrico deterministicnetworkinformationflowsusingpolylinkingsystems |