Discrete disordered systems: extremes, algorithms, and optimization.

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

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

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