Title :
Minimum Cost Integral Network Coding
Author :
Tao Cui ; Ho, T.
Author_Institution :
California Inst. of Technol., Pasadena
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;
Conference_Titel :
Information Theory, 2007. ISIT 2007. IEEE International Symposium on
Conference_Location :
Nice
Print_ISBN :
978-1-4244-1397-3
DOI :
10.1109/ISIT.2007.4557632