CaltechAUTHORS
  A Caltech Library Service

Minimum Cost Integral Network Coding

Cui, Tao and Ho, Tracey (2007) Minimum Cost Integral Network Coding. In: 2007 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, pp. 2736-2740. ISBN 978-1-4244-1397-3. https://resolver.caltech.edu/CaltechAUTHORS:20170425-161810594

[img] PDF - Published Version
See Usage Policy.

426kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170425-161810594

Abstract

In this paper, we consider finding a minimum cost multicast subgraph with network coding, where the rate to inject packets on each link is constrained to be integral. In the usual minimum cost network coding formulation, the optimal solution cannot always be integral. Fractional rates can be well approximated by choosing the time unit large enough, but this increases the encoding and decoding complexity as well as delay at the terminals. We formulate this problem as an integer program, which is NP-hard. A greedy algorithm and an algorithm based on linear programming rounding are proposed, which have approximation ratios k and 2k respectively, where k is the number of sinks. Moreover, both algorithms can be decentralized. We show by simulation that our algorithms' average performance substantially exceeds their bounds on random graphs.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ISIT.2007.4557632DOIArticle
http://ieeexplore.ieee.org/document/4557632/PublisherArticle
Additional Information:© 2007 IEEE. This work has been supported in part by DARPA grant N66001-06-C-2020, Caltech's Lee Center for Advanced Networking and a gift from Microsoft Research.
Funders:
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)N66001-06-C-2020
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Microsoft ResearchUNSPECIFIED
DOI:10.1109/ISIT.2007.4557632
Record Number:CaltechAUTHORS:20170425-161810594
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170425-161810594
Official Citation:T. Cui and T. Ho, "Minimum Cost Integral Network Coding," 2007 IEEE International Symposium on Information Theory, Nice, 2007, pp. 2736-2740. doi: 10.1109/ISIT.2007.4557632
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:76926
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:26 Apr 2017 01:35
Last Modified:15 Nov 2021 17:03

Repository Staff Only: item control page