Approximation Algorithms via Linear Programming

通过线性规划的近似算法

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

Most combinatorial optimization problems are NP-hard, and hence unlikely to have a polynomial-time algorithm that finds an optimal solution. This project investigates the design of algorithms that find near-optimal solutions but also come with a guarantee that the solution is not too much worse than optimal. This research investigates algorithms that produce solutions guaranteed to be nearly-optimal by relying on information contained in the optimal solution to 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. The research focuses on several specific areas in which computational experience has indicated that particular linear programming relaxations provide strong bounds and attempts to build on this to design approximation algorithms with good performance guarantees and good practical performance. Scheduling problems arise in a cross- section of applications, and the proposal focuses on several basic scheduling models, with the aim of developing algorithmic techniques that are not particularly application specific. Facility location problems are a type of network design problem in which the aim is to build a distribution network consisting of facilities and routes used to serve clients from the facilities. Known relaxations produce extremely high-quality bounds and the research will attempt to provide some theoretical justification for this, as well to devise new algorithms that also build on these. The traveling salesman problem is per haps the canonical optimization problem, and this investigation will try to resolve a well-known conjecture on the strength of the so called Held-Karp lower bound. For the bin-packing problem, this research will focus on a conjecture that there exists a polynomial-time algorithm that uses at most a constant extra bins, and is based on the cutting-stock LP formulation. For some other problems, such as the maximum acyclic sub-graph problem, in addition to the LP-based approach described above, this investigation will also explore algorithms based on convex programming relaxations, which have recently been used to strengthen linear relaxations in some settings. The ultimate goal of this research is to devise algorithms that will not just complement the ongoing computational work in polyhedral combinatorics with a theoretical foundation, but will also develop algorithmic implementations to solve these applications more easily.***

大多数组合优化问题是NP难的，因此不太可能有找到最优解的多项式时间算法。这个项目研究了算法的设计，这些算法可以找到接近最优的解决方案，但也保证解决方案不会比最优差太多。本研究利用线性规划松弛的最优解中所包含的信息，研究产生保证近乎最优解的算法。这些结果的一个结果是为这些线性规划松弛所给出的界的强度提供了理论上的证明。通过给出的算法可以证明所找到的解具有相对接近Lp界的值，还表明解的相对误差(与整数最优解相比)也很小。此外，过去的经验表明，设计具有这种性能保证的算法所需的洞察力也可以导致具有优越的经验性能的算法。研究集中在计算经验表明特定线性规划松弛提供强界的几个特定领域，并试图在此基础上设计具有良好性能保证和良好实用性能的近似算法。调度问题出现在不同的应用程序中，该提案集中在几个基本的调度模型上，目的是开发不是特别针对应用程序的算法技术。设施选址问题是一类网络设计问题，其目标是建立一个由设施和路线组成的配送网络，用于从设施向客户提供服务。已知的松弛会产生极高质量的边界，这项研究将试图为这一点提供一些理论上的理由，以及设计也建立在这些基础上的新算法。旅行商问题可能是一个典型的最优化问题，本文试图利用所谓的Hold-Karp下界来解决一个著名的猜想。对于装箱问题，本文将主要研究一个猜想，即存在一个多项式时间算法，该算法至多使用一个固定的额外装箱数，并且基于下料LP公式。对于其他一些问题，如最大非循环子图问题，除了上述基于LP的方法外，本研究还将探索基于凸规划松弛的算法，这种算法最近在某些设置下被用来加强线性松弛。这项研究的最终目标是设计算法，不仅为多面体组合数学中正在进行的计算工作提供理论基础，而且还将开发算法实现，以更容易地解决这些应用。*