CENTRAL LIMIT THEOREMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS ON SPARSE ERDOS-RENYI GRAPHS

• 成果类型: Article
• 署名作者: Cao, Sky
• 署名单位: Stanford University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1630
• 发表日期: 2021
• 页码: 1687-1723
• 关键词: minimal spanning-trees; zeta(2) limit; edge cover; PROOF; conjecture

摘要

For random combinatorial optimization problems, there has been much progress in establishing laws of large numbers and computing limiting constants for the optimal values of various problems. However, there has not been as much success in proving central limit theorems. This paper introduces a method for establishing central limit theorems in the sparse graph setting. It works for problems that display a key property which has been variously called endogeny, long-range independence and replica symmetry in the literature. Examples of such problems are maximum weight matching, lambda-diluted minimum matching, and optimal edge cover.