CAREER: Overcoming limitations to approximating combinatorial optimization problems

这一建议旨在全面了解组合优化问题的近似算法的局限性。组合优化问题在运筹学、机器学习、超大规模集成电路设计、计算生物学和统计物理等领域具有重要意义。为组合优化问题寻找算法的任务出现在无数应用中，从数十亿美元的运算到日常计算任务。许多优化问题是NP难的，因此除非P=NP，否则不能在多项式时间内精确地求解。然而，大多数这类问题都是实际应用中的关键因素，在实际应用中，如果很难找到最优解，就会产生近似解。提出的研究将研究唯一博弈猜想提出的近似算法的局限性，以及不太可能的最坏情况实例的存在带来的限制。PI的目标是设计一种方法，通过解决这两个因素来部分或完全克服这些限制。该提案概述了一项具有挑战性的计划，重点是研究谱图理论、凸优化、多种商品流动和调和分析的广泛领域。这项工作的贡献将对可逼近理论和现实世界问题产生重大影响，这些问题将为半随机实例提供高效、准确的算法，并将自然地导致许多不同领域的研究人员之间的合作，如数学、计算机科学理论、工业工程、运筹学和网络。

This proposal seeks to develop a comprehensive understanding of the limitations of approximation algorithms for combinatorial optimization problems. Combinatorial optimization problems are of great importance to various areas such as operations research, machine learning, VLSI design, computational biology and statistical physics. The task of finding algorithms for combinatorial optimization problems arise in countless applications, from billion-dollar operations to everyday computing tasks. Many optimization problems are NP-hard and thus cannot be solved exactly in polynomial time unless P=NP. However, the majority of such problems are key elements to practical applications where often, if the optimal solution is hard to find, producing an approximate solution su;ffices.The research proposed will study the limitations of approximation algorithms posed by the Unique Games Conjecture and the limitations posed by the presence of unlikely worst-case instances. The PI aims to design a methodology to partially or fully overcome such limitations by addressing both of those factors. The proposal outlines a challenging plan focusing on research in a broad cross-section of spectral graph theory, convex optimization, multi-commodity flows, and harmonic analysis. The contributions of the work described in this proposal will have great impact on the theory of approximability as well as real world problems for which efficient, exact algorithms will be provided for semi-random instances and will naturally result in collaborations between researchers across many different fields such as mathematics, theory of computer science, industrial engineering, operations research and networking.