AF: Small: Approximation Techniques for Combinatorial Optimization

AF：小：组合优化的近似技术

• 批准号: 1565581
• 负责人: Moses Charikar
• 金额: $ 13.06万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1565581&HistoricalAwards=false
• 关键词: AF; Small; Approximation; Techniques; Combinatorial

Approximation techniques are valuable in the design of algorithms for combinatorial optimization problems. Mathematical programming relaxations provide tractable versions of hard optimization problems that are useful in the design of good algorithms -- in some cases, these relaxations and their duals serve as a guide for the design of algorithms and lower bound proofs. Such approximation techniques are useful not just in traditional optimization problems, but also for problems in online algorithms and other areas. This project proposes to study a variety of problems where approximation techniques play a crucial role -- many of these questions are about basic problems in approximation algorithms, but many are about questions where insights from mathematical relaxations and other approximation techniques play an important role. The broad goals of this project include (a) Obtaining a better understanding of the use of lift-and-project relaxations for optimization problems like coloring and the closely related question of developing algorithmic techniques for graphs of low threshold rank, (b) Attempting to close gaps in our understanding of classical optimization problems like the traveling salesman problem and bin packing, and (c) Shedding light on newer problems like online versions of weighted matching and new flow formulations.Optimization problems are ubiquitous and for many such problems of interest, we have strong evidence that it is impossible to obtain exact efficient solutions. To circumvent this intractability, we design efficient heuristics that may not find the best solution necessarily, but have guarantees that the solution they produce is not far from the optimal (i.e. is approximately optimal). Mathematical programming is a very important tool in designing such approximation algorithms. Successfully achieving the project goals will require advances in our knowledge of this area, and especially new insights into the powerful and versatile mathematical programming toolkit. As part of this project, graduate and undergraduate students will be trained by involving them in these research activities. Course materials for graduate and undergraduate courses will be developed distilling research results of this project, as well as new developments in the field.

近似技术在组合优化问题的算法设计中很有价值。数学编程松弛提供了可访问的硬性优化问题，这些问题可用于设计良好算法的设计 - 在某些情况下，这些放松及其双重偶数是设计算法和下限证明的指南。这种近似技术不仅在传统优化问题中很有用，而且对在线算法和其他领域的问题也很有用。该项目建议研究各种近似技术起着至关重要的作用的问题 - 其中许多问题是关于近似算法中的基本问题，但是许多问题是关于数学放松和其他近似技术的见解的问题。该项目的广泛目标包括（a）更好地理解提升和项目放松的使用，以进行优化问题，例如着色和与较低阈值等级的算法技术开发算法技术紧密相关的问题，（（b）试图在我们对经典优化问题（例如旅行人员问题和在线）中的差距中的理解来弥合差距，以及（c）新的问题，以及（c）新的问题。配方。优化问题无处不在，对于许多此类感兴趣的问题，我们有强有力的证据表明不可能获得精确的有效解决方案。为了避免这种棘手的性能，我们设计了可能不一定要找到最佳解决方案的有效启发式方法，但保证它们产生的解决方案距离最佳距离不远（即大约是最佳的）。数学编程是设计这种近似算法的非常重要的工具。成功实现项目目标将需要我们对这一领域的了解，尤其是对功能强大且多功能的数学编程工具包的新见解。作为该项目的一部分，将通过让他们参与这些研究活动来培训研究生和本科生。研究生和本科课程的课程材料将开发出该项目的研究结果以及该领域的新发展。