权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CAREER: Metric Geometry Techniques for Approximation Algorithms

职业：近似算法的度量几何技术

基本信息

批准号：
1150062
负责人：
Yury Makarychev
金额：
$ 50万
依托单位：
Toyota Technological Institute at Chicago
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2012
资助国家：
美国
起止时间：
2012-07-01 至 2018-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1150062&HistoricalAwards=false
关键词：
CAREER Metric Geometry Techniques Approximation

项目摘要

Combinatorial optimization problems are of great importance to numerous applications. They arise in operations research, machine learning, VLSI design, computational biology and many other areas. Many optimization problems however are NP-hard and thus cannot be solved exactly in polynomial time unless P=NP. It is natural therefore to look for approximation algorithms, efficient algorithms that find only approximate solutions. Design and analysis of approximation algorithms is a very active research area. Various approaches for solving combinatorial optimization problems have appeared in the last three decades. However, despite significant progress, many important problems are still open. This research project aims to advance the application of metric geometry techniques for solving combinatorial optimization problems, investigate new methods for designing approximation algorithms, and develop tools for analyzing the performance of approximation algorithms on real-life instances. This research project will be both theoretically important and practically relevant and it will lead to development of approximation algorithms for important applied problems that occur in many fields of science and engineering. Specifically, the PI will work on the following problems.* Traditionally most research has focused on analyzing the worst case performance of approximation algorithms. However, practitioners observe that instances of combinatorial optimization problems that arise in practice are often not as hard as worst case instances. The PI will study semi-random models for various combinatorial optimization problems, and develop approximation algorithms that perform well on semi-random instances. This can perhaps explain what we see in practice.* Recent research in the hardness of approximation initiated by Khot identified Unique Games Problem as a combinatorial obstacle to the development of approximation algorithms for many problems. The PI will study algorithmic techniques for solving the Unique Games Problem.* The PI will study lift-and-project hierarchies of linear programming (LP) and semi-definite programming (SDP) relaxations, analyze their integrality gaps, and design subexponential approximation algorithms that use these hierarchies.* There is a close connection between some areas of theoretical computer science and pure mathematics. To settle down some problems in combinatorial optimization, we need to resolve closely connected open problems in analysis. The PI will explore several problems with deep ties to computer science and mathematics.

组合优化问题在许多应用中具有重要意义。它们出现在运筹学、机器学习、超大规模集成电路设计、计算生物学和许多其他领域。然而，许多优化问题是NP难的，因此除非P=NP，否则无法在多项式时间内精确求解。这是自然的，因此，寻找近似算法，有效的算法，只找到近似的解决方案。近似算法的设计和分析是一个非常活跃的研究领域。在过去的三十年里，出现了各种解决组合优化问题的方法。然而，尽管取得了重大进展，许多重要问题仍然悬而未决。本研究项目旨在推进度量几何技术在解决组合优化问题中的应用，研究设计近似算法的新方法，并开发用于分析近似算法在实际情况下的性能的工具。这个研究项目将是理论上重要的和实际相关的，它将导致发展的近似算法的重要应用问题，发生在许多领域的科学和工程。具体来说，PI将解决以下问题。*传统上，大多数研究都集中在分析近似算法的最坏情况下的性能。然而，实践者观察到，在实践中出现的组合优化问题的实例往往不如最坏情况下的实例那么难。PI将研究各种组合优化问题的半随机模型，并开发在半随机情况下表现良好的近似算法。这也许可以解释我们在实践中看到的情况。最近的研究在硬度的近似霍特发起确定唯一的游戏问题作为一个组合的障碍，发展的近似算法的许多问题。PI将研究解决唯一博弈问题的算法技术。PI将研究线性规划（LP）和半定规划（SDP）松弛的提升和投影层次，分析它们的完整性差距，并设计使用这些层次的次指数近似算法。理论计算机科学和纯数学的某些领域之间有着密切的联系。为了解决组合优化中的一些问题，需要解决分析中紧密相连的开放问题。PI将探索与计算机科学和数学有着深刻联系的几个问题。