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.