Approximation Algorithms via Linear Programming

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

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.***