DocumentCode :
2031488
Title :
Minimum Cost Integral Network Coding
Author :
Tao Cui ; Ho, T.
Author_Institution :
California Inst. of Technol., Pasadena
fYear :
2007
fDate :
24-29 June 2007
Firstpage :
2736
Lastpage :
2740
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.
Keywords :
encoding; greedy algorithms; integer programming; linear programming; greedy algorithm; integer program; linear programming; minimum cost integral network coding; random graphs; Approximation algorithms; Capacity planning; Cost function; Decoding; Delay effects; Encoding; Greedy algorithms; Heuristic algorithms; Linear programming; Network coding;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory, 2007. ISIT 2007. IEEE International Symposium on
Conference_Location :
Nice
Print_ISBN :
978-1-4244-1397-3
Type :
conf
DOI :
10.1109/ISIT.2007.4557632
Filename :
4557632
Link To Document :
بازگشت