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