Large Random Structures and Network Flow

点击翻译按钮获取中文摘要

The central theme of the project is study of optimal flows through networks, where different aspects of the network (topology, edge-capacities, costs) may be random. Several different methodologies will be brought to bear: a probabilistic reformulation of the cavity method from statistical physics, local weak convergence for establishing existence of limits as network size grows, as well as more standard techniques from probabilistic combinatorics and random graphs. Some of these techniques will also be applied to various combinatorial optimization problems over random data, examining a conjecture relating computational hardness of problem to structure of near-optimal solutions.Network flow problems have been studied in many different disciplines: Electrical Engineering, Computer Science, Operations Research, Transportation Engineering, Regional Economics. The proposal initiates systematic mathematical study of abstracted models of these problems in the context of random networks, where randomness is used to capture the idea of networks not being centrally designed. Mathematicians have techniques for studying very large systems without doing exact calculations (which become more difficult as systems get larger) which are separate from the techniques more familiar to engineers. The broader impacts envisaged are facilitating the spread of techniques between different research communities and providing additional tools for the design of large networks.