CAREER: Overcoming limitations to approximating combinatorial optimization problems

该建议旨在全面了解组合优化问题的近似算法的局限性。组合优化问题在运筹学、机器学习、超大规模集成电路设计、计算生物学和统计物理学等领域都具有重要意义。为组合优化问题寻找算法的任务出现在无数的应用中，从数十亿美元的操作到日常计算任务。许多优化问题是NP难的，因此除非P=NP，否则无法在多项式时间内精确求解。然而，大多数这样的问题是关键因素，往往在实际应用中，如果最优解是很难找到，产生一个近似的解决方案sufficies.The研究提出将研究的唯一博弈猜想所造成的近似算法的局限性和不太可能的最坏情况下的存在所造成的限制。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.