Discrete disordered systems: extremes, algorithms, and optimization.

离散无序系统：极值、算法和优化。

• 批准号: RGPIN-2017-04330
• 负责人: AddarioBerry, Dana
• 金额: $ 2.7万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=710497
• 关键词: Discrete; disordered; systems; extremes; algorithms

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.

优化是对极值的一种或另一种形式的研究，它在理论和应用科学探究中无处不在。在组合优化中，人们可能希望最小化访问一组固定城市时所走的总距离（旅行推销员问题），或者最小化确保从一个城市开车到任何另一个城市所需的沥青总里程（最小生成树问题）。在整数规划中，人们希望用最少的单元数来满足需求；也许是城市交通系统中需要的公共汽车数量，或者是完全覆盖城市所需的手机信号塔数量。举一个更有机的例子，考虑一下河流系统的轨迹，它在通往海洋的途中迂回曲折，绕过障碍物。河流的路线不是欧几里得最短路径，但它是最优的，至少在局部，它近似地最小化了水从源头到海洋的轨迹所消耗的能量。