The Design, Analysis and Application of Approximation Algorithms

逼近算法的设计、分析与应用

• 批准号: 9912422
• 负责人: David Shmoys
• 金额: $ 27.08万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-07-01 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9912422&HistoricalAwards=false
• 关键词: Design; Analysis; Application; Approximation; Algorithms

Proposal-9912422PI: David ShmoysMost combinatorial optimization problems that arise in applications from scheduling, logistics, and network design, for example, are NP-hard, and hence unlikely to have a polynomial-time algorithm that finds an optimal solution. This project is focused on the study of approximation algorithms for these problems, where the aim is to design effective algorithms that are guaranteed to produce near-optimal solutions, and typically produce solutions of extremely high quality.This project aims to further develop the three major techniques that have emerged as consistently producing superior results: rounding techniques based on mathematical programming relaxations, primal-dual methods, and local search methods. Although there has been significant progress, there are many problems for which the current state of knowledge is not sufficient. This project is devoted to the investigation of several problems in this area.The primary focus of this work is to investigate algorithms that produce solutions guaranteed to be nearly-optimal by relying on information contained in the optimal solution to a linear programming relaxation. One consequence of such results would be to provide a theoretical justification for the strength of the bounds given by these linear programming relaxations. By giving algorithms for which one can prove that the solution found has value relatively close to the LP bound, one also shows that relative error of the solution (compared to the integer optimum) is also small. Furthermore, past experience has shown that the insight needed to devise algorithms with such performance guarantees can also lead to algorithms with superior empirical performance.This work focuses on several specific areas to attempt to design approximation algorithms with good performance guarantees and good practical performance. Facility location, clustering problems, and scheduling problems arise in a number of application settings, including computational biology and project resource management, and this project considers a number of basic models, with the aim of developing algorithmic techniques that are not particularly application specific.For several basic problems including the k-median problem, the uncapacitated facility location problem, the bin-packing problem, and the problem of scheduling jobs on parallel machines subject to precedence constraints, the aim of this work is to design algorithms with superior performance than was known previously.Polyhedral methods are the foremost techniques used to find optimal solutions to hard discrete optimization problems. These methods require the solution of a series of linear programming relaxations. Heuristic methods that rely on linear programming can be easily integrated into this approach, with the aim of speeding up these methods, since they can take advantage of the work already done is solving these linear programs. This work also studies the efficacy of such heuristics in enhancing the polyhedral methods to solving (to optimality) these problems.

Proposal-9912422PI：David Shmoys例如，在调度、物流和网络设计的应用中出现的大多数组合优化问题都是NP难的，因此不太可能有找到最优解的多项式时间算法。本项目致力于这些问题的近似算法的研究，目的是设计有效的算法，保证产生接近最优解，并且通常产生极高质量的解。本项目旨在进一步发展三大技术：基于数学规划松弛的舍入技术、原对偶方法和局部搜索方法。虽然取得了重大进展，但仍存在许多问题，目前的知识状况还不足以解决这些问题。本项目致力于研究这一领域中的几个问题，主要的工作是研究通过依赖于线性规划松弛的最优解中包含的信息来产生保证解的近最优解的算法。这些结果的一个结果是为这些线性规划松弛所给出的界的强度提供了理论上的证明。通过给出的算法可以证明所找到的解具有相对接近Lp界的值，还表明解的相对误差(与整数最优解相比)也很小。此外，过去的经验表明，设计具有这样的性能保证的算法所需要的洞察力也可以导致具有更好的经验性能的算法。本工作集中在几个特定的领域，试图设计具有良好的性能保证和良好的实际性能的近似算法。在计算生物学和项目资源管理等许多应用背景下，设备选址、聚类和调度问题都会出现，本项目考虑了一些基本模型，目的是开发不是特别适用的算法技术。对于几个基本问题，包括k-Medium问题、无能力设施选址问题、装箱问题和受优先约束的并行机上的作业调度问题，本工作的目的是设计具有比已知更好的性能的算法。多面体方法是用于寻找硬离散优化问题的最优解的最重要的技术。这些方法需要解决一系列线性规划松弛问题。依赖于线性规划的启发式方法可以很容易地集成到这种方法中，目的是加快这些方法的速度，因为它们可以利用已经完成的工作来求解这些线性规划。这项工作还研究了这种启发式方法在增强多面体方法解决这些问题(达到最优性)方面的有效性。