Deterministic network coding by matrix completion

ABSTRACT

We present a new deterministic algorithm to construct network codes for multicast problems, a particular class of network information ow problems. Our algorithm easily generalizes to several variants of multicast problems. Our approach is based on a new algorithm for maximum-rank completion of mixed matrices---taking a matrix whose entries are a mixture of numeric values and symbolic variables, and assigning values to the variables so as to maximize the resulting matrix rank. Our algorithm is faster than existing deterministic algorithms and can operate over a smaller field.

REFERENCES

• 1: R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204--1216, 2000.
• 2: M. Berdan. A matrix rank problem. Unpublished manuscript, 2003.
• 3: William H Cunningham, Improved bounds for matroid partition and intersection algorithms, SIAM Journal on Computing, v.15 n.4, p.948-957, Nov. 1986 [doi>10.1137/0215066]
• 4: S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:111--121, 1980.
• 5: S. Fujishige. Submodular Functions and Optimization, volume 47 of Annals of Discrete Mathematics. North-Holland, 1991.
• 6: Harold N. Gabow , Ying Xu, Efficient theoretic and practical algorithms for linear matroid intersection problems, Journal of Computer and System Sciences, v.53 n.1, p.129-147, Aug. 1996 [doi>10.1006/jcss.1996.0054]
• 7: J. F. Geelen. Maximum rank matrix completion. Linear Algebra and its Applications, 288:211--217, 1999.
• 8: J. F. Geelen. Matching theory. Unpublished manuscript, 2001.
• 9: N. J. A. Harvey, R. D. Kleinberg, and A. R. Lehman. Comparing network coding with multicommodity flow for the k-pairs communication problem. Technical Report MIT-LCS-TR-964, Massachusetts Institute of Technology, Sept. 2004.
• 10: T. Ho, D. R. Karger, M. Médard, and R. Koetter. Network coding from a network flow perspective. In Proceedings of the IEEE International Symposium on Information Theory, 2003.
• 11: T. Ho, R. Koetter, M. Médard, D. R. Karger, and M. Effros. The benefits of coding over routing in a randomized setting. In Proceedings of the IEEE International Symposium on Information Theory, 2003.
• 12: S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory. Submitted July 2003.
• 13: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 14: M. Laurent. Matrix completion problems. In C. Floudas and P. Pardalos, editors, The Encyclopedia of Optimization, volume III, pages 221--229. Kluwer, 2001.
• 15: April Rasala Lehman , Eric Lehman, Complexity classification of network information flow problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 16: S.-Y. R. Li, R. Yeung, and N. Cai. Linear network coding. IEEE Transactions on Information Theory, 49(2), 2003.
• 17: L. Lovász. On determinants, matchings and random algorithms. In L. Budach, editor, Fundamentals of Computation Theory, FCT '79. Akademie-Verlag, Berlin, 1979.
• 18: K. Murota. Matrices and Matroids for Systems Analysis. Springer-Verlag, 2000.
• 19: A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, 2003.