The Design, Analysis and Application of Approximation Algorithms

提案- 9912422pi: David shmoys例如，在调度、物流和网络设计等应用程序中出现的大多数组合优化问题都是np困难的，因此不太可能有找到最优解的多项式时间算法。这个项目的重点是研究这些问题的近似算法，其目的是设计有效的算法，保证产生接近最优的解决方案，并且通常产生极高质量的解决方案。该项目旨在进一步发展已经出现的三种主要技术，这些技术一直产生卓越的结果：基于数学规划松弛的舍入技术、原始对偶方法和局部搜索方法。尽管已经取得了重大进展，但仍有许多问题，目前的知识水平是不够的。这个项目致力于研究这个领域的几个问题。这项工作的主要重点是研究通过依赖线性规划松弛的最优解中包含的信息来产生保证接近最优解的算法。这些结果的一个结果是为这些线性规划松弛所给出的界的强度提供了理论依据。通过给出可以证明所找到的解具有相对接近LP界的值的算法，还可以证明该解的相对误差（与整数最优相比）也很小。此外，过去的经验表明，设计具有这种性能保证的算法所需的洞察力也可以导致具有优越经验性能的算法。本工作着重于几个特定的领域，试图设计具有良好性能保证和良好实际性能的近似算法。设施位置、集群问题和调度问题出现在许多应用程序设置中，包括计算生物学和项目资源管理，本项目考虑了许多基本模型，目的是开发非特定于应用程序的算法技术。对于k-中值问题、无能力设施定位问题、装箱问题和受优先约束的并行机器上的作业调度问题等几个基本问题，本工作的目的是设计具有比以前已知性能更好的算法。多面体方法是用于寻找离散优化问题最优解的最重要技术。这些方法需要求解一系列的线性规划松弛。依赖于线性规划的启发式方法可以很容易地集成到这种方法中，目的是加快这些方法的速度，因为它们可以利用已经完成的工作来求解这些线性规划。本工作还研究了这种启发式方法在增强多面体方法解决这些问题（优化）方面的功效。

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.