Discrete disordered systems: extremes, algorithms, and optimization.

最优化是对极值的研究--以这样或那样的形式，它在理论和应用科学研究中无处不在。在组合优化中，人们可能希望最小化访问一组固定城市时的总行程(旅行商问题)或确保从一个城市开车到任何另一个城市所需的总沥青里程(最小生成树问题)。在整数规划中，人们希望用最少的单位数来满足需求；可能是城市交通系统所需的公交车数量，或者是覆盖整个城市所需的基站数量。对于一个更自然的例子，考虑一下河流系统的轨迹，它们在通往海洋的途中扭曲和绕过障碍物。河流的路径不是欧几里得最短路径，但它是最优的，因为至少在局部，它近似地最小化了从源头到海洋的轨迹中的水所消耗的能量。不同的优化问题在算法难度上存在巨大差异。然而，算法的最差性能往往不能很好地衡量其在现实世界问题中的效率，因为在现实世界中，输入是大量独立因素之间复杂交互作用的产物。这就是我的研究项目背后的动力，该项目专注于分析和开发随机数据优化问题的算法。值得注意的是，对许多优化问题的概率分析直接通向现代概率的核心；通常，在描述不同的物理、生物和信息系统时，相同的概率模型出现。指出这种“普遍的”行为是现代概率必须向科学提供的关键概念见解之一。*我打算回答的一些具体问题是：*对于哪些随机数据上的优化问题，全局渐近行为本质上由局部相互作用决定？在这种情况下，它意味着什么涨落大小？*许多约束满足问题(CSP)被期望服从自旋眼镜的所谓的1-副本对称破坏启发式。这对应于一个非常简单的关联结构，相当于分支过程中的极值。有没有一种系统的方法来从CSP描述中逆向设计关联结构？这将为随机数据上的硬CSP产生有效的近似算法。*对数相关的高斯随机场中的极大值行为是否可以预测更一般的对数相关场的行为？马尔可夫随机场中极值的精细行为是什么？*随机数据上的组合优化问题是否存在大偏差理论？*在分支系统中，资源竞争如何影响前沿传播速度？这与非局部Fisher-KPP型积分微分方程解的涨落有关。

Optimization is the study of extreme values – in one form or another, it is ubiquitous in both theoretical and applied scientific inquiry. In combinatorial optimization one might wish to minimize the total distance travelled when visiting a fixed set of cities (the travelling salesman problem) or the total miles of asphalt required to ensure one can drive from one city to any other (the minimum spanning tree problem). In integer programming one wishes to satisfy demand using a minimum number of units; perhaps, the number of busses needed in an urban transit system, or the number of cell towers required for full coverage of a city. For a more organic example, consider the trajectories of river systems, which twist and turn around obstacles en route to the ocean. A river's route is not a Euclidean shortest path, but it is optimal in that, at least locally, it approximately minimizes the energy expended by the water in its trajectory from source to sea.******There are vast differences in algorithmic difficulty for different optimization problems. However, the worst-case performance of an algorithm is often a poor gauge of its efficiency for real-world problems where the input is the product of complex interactions between large numbers of independent factors. This is the impetus behind my research program, which focusses on the analysis and development of algorithms for optimization problems on random data. Remarkably, the probabilistic analysis of many optimization problems leads directly to the heart of modern probability; often, the same probabilistic models arise in describing diverse physical, biological and information systems. Pointing out such “universal” behavior is one of the key conceptual insights that modern probability has to offer to the sciences. ******Some of the specific questions I aim to answer are: **** For which optimization problems over random data is global asymptotic behavior essentially determined by local interactions? When this is the case, what does it imply about fluctuation sizes? **** Many constraint satisfaction problems (CSPs) are expected to obey the so called 1-replica symmetry breaking heuristic from spin glasses. This corresponds to a very simple correlation structure, equivalent to that of extremes in branching processes. Is there a systematic way of reverse-engineering the correlation structure from the CSP description? This would yield efficient approximation algorithms for hard CSPs on random data. **** Does the now-well-understood behavior of maxima in log-correlated Gaussian random fields predict that of more general log-correlated fields? What is the fine behavior of extremes in Markov random fields?**** Is there a large deviations theory for combinatorial optimization problems over random data? **** How does competition for resources affect front propagation speed in branching systems? This relates to the fluctuations of nonlocal Fisher-KPP type integrodifferential equations.