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.