Combinatorial and Algorithmic Aspects of Network Coding

带宽的有效使用将是决定下一代互联网可扩展性的关键因素。 研究人员研究的问题是，通过赋予节点在传输过程中对信息进行编码和解码的能力，网络中获得了多少效率，这种模式被称为网络编码。 该研究旨在更全面地了解结构复杂网络中网络编码的能力和局限性，使用算法理论，组合优化和计算复杂性的工具来实现。 该研究描绘了网络编码研究中的算法和组合优化理论的作用，结合了近似算法和原始对偶技术等核心概念。 精确的算法计算可达到的速率区域寻求在特殊类别的网络编码问题，最显着的多个单播会话无向图。近似算法寻求一般的图形，它是可能的，非平凡的近似算法将突出纯粹的网络编码问题的结构特征（例如简洁的不可行性证书），这将刺激在该领域的进一步进展。 网络编码率和其他图形参数之间的关系，包括最大并发多商品流量和参数的基础上的边缘切割，将被探讨。 最后，研究调查了可实现的 速率区域的网络编码问题，其中节点有界存储。

The efficient use of bandwidth will be a critical factor in determining the scalability of the next-generation Internet. The investigator studies the question of how much efficiency is gained in a network by giving nodes the capability to encode and decode information in the process of transmitting it, a paradigm known as network coding. The research aims for a more complete understanding of the capabilities and limitations of network coding in structurally complex networks, to be achieved using tools from the theory of algorithms, combinatorial optimization, and computational complexity. The research delineates a role for the theory of algorithms and combinatorial optimization within the study of network coding, incorporating core notions such as approximation algorithms and primal-dual techniques. Exact algorithms for computing the achievable rate region are sought in special classes of network coding problems, most notably for multiple unicast sessions in undirected graphs. Approximation algorithms are sought for general graphs; it is likely that non-trivial approximation algorithms will highlight purely structural features of network coding problems ( e.g. succinct certificates of infeasibility) which will spur further progress in the area. The relationship between network coding rates and other graph parameters, including the maximum concurrent multicommodity flow rate and parameters based on edge cuts, will be explored. Finally, the research investigates the achievable rate region for network coding problems in which nodes have bounded storage.