An Algorithmic Framework for Wireless Information Flow
We consider the wireless relay network model as introduced by Avestimehr, Diggavi and Tse for approximating Gaussian relay channels and show that it is a special case of a more abstract flow model that we introduce in this paper. This flow model is based on linking systems, a combinatorial structure...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/60563 https://orcid.org/0000-0002-0520-1165 |
| _version_ | 1826188216484495360 |
|---|---|
| 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 | We consider the wireless relay network model as introduced by Avestimehr, Diggavi and Tse for approximating Gaussian relay channels and show that it is a special case of a more abstract flow model that we introduce in this paper. This flow model is based on linking systems, a combinatorial structure with a tight connection to matroids. A main advantage of this flow model is that properties and algorithms can easily be derived from existing theory on matroids and linking systems. In particular we show a max-flow min-cut theorem and submodularity of cuts. Furthermore, efficient algorithms for matroid intersection or for matroid partition can be used for finding a maximum flow and a minimum cut. Thus, this approach can profit from well-established matroid (intersection or partition) algorithms, leading to faster algorithms for large capacity networks. Another advantage of our approach is that it is easy to extend or adapt it to similar problems. In particular, the algorithm we present for finding maximum flows can easily be adapted to find a maximum flow with minimum costs when costs are introduced on the inputs and outputs of the relays. |
| first_indexed | 2024-09-23T07:56:19Z |
| format | Article |
| id | mit-1721.1/60563 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T07:56:19Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/605632022-09-30T01:06:47Z An Algorithmic Framework for Wireless Information Flow Goemans, Michel X. Iwata, Satoru Zenklusen, Rico Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Goemans, Michel X. We consider the wireless relay network model as introduced by Avestimehr, Diggavi and Tse for approximating Gaussian relay channels and show that it is a special case of a more abstract flow model that we introduce in this paper. This flow model is based on linking systems, a combinatorial structure with a tight connection to matroids. A main advantage of this flow model is that properties and algorithms can easily be derived from existing theory on matroids and linking systems. In particular we show a max-flow min-cut theorem and submodularity of cuts. Furthermore, efficient algorithms for matroid intersection or for matroid partition can be used for finding a maximum flow and a minimum cut. Thus, this approach can profit from well-established matroid (intersection or partition) algorithms, leading to faster algorithms for large capacity networks. Another advantage of our approach is that it is easy to extend or adapt it to similar problems. In particular, the algorithm we present for finding maximum flows can easily be adapted to find a maximum flow with minimum costs when costs are introduced on the inputs and outputs of the relays. National Science Foundation (U.S.) (contract CCF-0829878) United States. Office of Naval Research (grant N00014-05-1-0148) 2011-01-14T13:46:57Z 2011-01-14T13:46:57Z 2010-01 2009-09 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-5870-7 INSPEC Accession Number: 11135249 http://hdl.handle.net/1721.1/60563 Goemans, M.X., S. Iwata, and R. Zenklusen. “An algorithmic framework for wireless information flow.” Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on. 2009. 294-300. © Copyright 2009 IEEE https://orcid.org/0000-0002-0520-1165 en_US http://dx.doi.org/10.1109/ALLERTON.2009.5394810 Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, 2009. Allerton 2009. 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 |
| spellingShingle | Goemans, Michel X. Iwata, Satoru Zenklusen, Rico An Algorithmic Framework for Wireless Information Flow |
| title | An Algorithmic Framework for Wireless Information Flow |
| title_full | An Algorithmic Framework for Wireless Information Flow |
| title_fullStr | An Algorithmic Framework for Wireless Information Flow |
| title_full_unstemmed | An Algorithmic Framework for Wireless Information Flow |
| title_short | An Algorithmic Framework for Wireless Information Flow |
| title_sort | algorithmic framework for wireless information flow |
| url | http://hdl.handle.net/1721.1/60563 https://orcid.org/0000-0002-0520-1165 |
| work_keys_str_mv | AT goemansmichelx analgorithmicframeworkforwirelessinformationflow AT iwatasatoru analgorithmicframeworkforwirelessinformationflow AT zenklusenrico analgorithmicframeworkforwirelessinformationflow AT goemansmichelx algorithmicframeworkforwirelessinformationflow AT iwatasatoru algorithmicframeworkforwirelessinformationflow AT zenklusenrico algorithmicframeworkforwirelessinformationflow |