The Design, Analysis and Application of Approximation Algorithms

提案-9912422 PI：大卫Shmoy例如，在调度、物流和网络设计等应用中出现的大多数组合优化问题都是NP难的，因此不太可能有找到最优解的多项式时间算法。该项目的重点是研究这些问题的近似算法，目的是设计有效的算法，保证产生接近最优的解决方案，通常产生极高质量的解决方案。该项目旨在进一步发展已经出现的三种主要技术，以不断产生上级结果：基于数学规划松弛、原始对偶方法和局部搜索方法的舍入技术。虽然取得了重大进展，但仍有许多问题是目前的知识状况所不足以解决的。这个项目致力于调查在这一领域的几个问题。这项工作的主要重点是调查的算法，产生的解决方案，保证是接近最佳的依赖于信息中包含的最佳解决方案的线性规划松弛。 这样的结果之一将是提供一个理论上的理由，这些线性规划松弛的界限的强度。 通过给出算法，可以证明找到的解决方案具有相对接近LP界的值，还表明解决方案的相对误差（与整数最优值相比）也很小。 此外，过去的经验表明，需要设计这样的性能保证算法的洞察力也可以导致算法具有上级的经验performance.This工作集中在几个特定的领域，试图设计近似算法具有良好的性能保证和良好的实际性能。设施定位、聚类问题和调度问题出现在许多应用环境中，包括计算生物学和项目资源管理，并且本项目考虑了许多基本模型，目的是开发不是特别特定于应用的算法技术。和具有优先约束的并行机调度问题，本文的目标是设计性能上级以往已知算法的算法.多面体方法是求解困难离散优化问题的最重要的技术. 这些方法需要解决一系列的线性规划松弛。依赖于线性规划的启发式方法可以很容易地集成到这种方法中，目的是加速这些方法，因为它们可以利用已经完成的工作来解决这些线性规划。 这项工作还研究了效率，这样的数学在提高多面体的方法来解决（最优）这些问题。

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.