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.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
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.
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)N66001-06-C-2020
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Microsoft ResearchUNSPECIFIED
Record Number:CaltechAUTHORS:20170425-161810594
Persistent URL:
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
Deposited By: Kristin Buxton
Deposited On:26 Apr 2017 01:35
Last Modified:15 Nov 2021 17:03

Repository Staff Only: item control page