On network coding capacity : matroidal networks and network capacity regions
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/62657 |
| _version_ | 1826216274665930752 |
|---|---|
| author | Kim, Anthony Eli |
| author2 | Muriel Médard. |
| author_facet | Muriel Médard. Kim, Anthony Eli |
| author_sort | Kim, Anthony Eli |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. |
| first_indexed | 2024-09-23T16:45:05Z |
| format | Thesis |
| id | mit-1721.1/62657 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:45:05Z |
| publishDate | 2011 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/626572019-04-12T16:10:28Z On network coding capacity : matroidal networks and network capacity regions Kim, Anthony Eli Muriel Médard. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. Cataloged from PDF version of thesis. Includes bibliographical references (p. 68-70). One fundamental problem in the field of network coding is to determine the network coding capacity of networks under various network coding schemes. In this thesis, we address the problem with two approaches: matroidal networks and capacity regions. In our matroidal approach, we prove the converse of the theorem which states that, if a network is scalar-linearly solvable then it is a matroidal network associated with a representable matroid over a finite field. As a consequence, we obtain a correspondence between scalar-linearly solvable networks and representable matroids over finite fields in the framework of matroidal networks. We prove a theorem about the scalar-linear solvability of networks and field characteristics. We provide a method for generating scalar-linearly solvable networks that are potentially different from the networks that we already know are scalar-linearly solvable. In our capacity region approach, we define a multi-dimensional object, called the network capacity region, associated with networks that is analogous to the rate regions in information theory. For the network routing capacity region, we show that the region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. For the network linear coding capacity region, we construct a computable rational polytope, with respect to a given finite field, that inner bounds the linear coding capacity region and provide exact algorithms and approximation heuristics for computing the polytope. The exact algorithms and approximation heuristics we present are not polynomial time schemes and may depend on the output size. by Anthony Eli Kim. M.Eng. 2011-05-09T15:15:31Z 2011-05-09T15:15:31Z 2010 2010 Thesis http://hdl.handle.net/1721.1/62657 713714210 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 70 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kim, Anthony Eli On network coding capacity : matroidal networks and network capacity regions |
| title | On network coding capacity : matroidal networks and network capacity regions |
| title_full | On network coding capacity : matroidal networks and network capacity regions |
| title_fullStr | On network coding capacity : matroidal networks and network capacity regions |
| title_full_unstemmed | On network coding capacity : matroidal networks and network capacity regions |
| title_short | On network coding capacity : matroidal networks and network capacity regions |
| title_sort | on network coding capacity matroidal networks and network capacity regions |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/62657 |
| work_keys_str_mv | AT kimanthonyeli onnetworkcodingcapacitymatroidalnetworksandnetworkcapacityregions |