Resolving Anomalies in Approximation Algorithms

组合优化中的许多问题都是NP难的，不太可能有有效的算法来寻找最优解。这些问题包括工业实践中出现的大量问题，包括为满足客户需求的设施定位、安排服务人员进行现场维修、调度车辆、构建具有特定连接特性的低成本网络、在芯片上布线等等。解决这些问题的典型方法是设计一些启发式算法，在实践中提供足够好的解，或者，如果有足够的时间和资源可用，并且最优解足够有价值，设计一个穷举搜索算法来找到最优解。为了从数学上为启发式算法的研究奠定基础，计算机科学家考虑了近似算法。这些都是高效的多项式时间算法，它们产生的解被证明在价值上接近最优解。具体地说，_-近似算法产生的解的值在最优解的值的因子_内。参数_有时被称为算法的性能保证。为了证明该算法产生了一个接近最优解，必须使用最优值的界。这个界限通常是一个本身就可以有效计算的量，在许多有趣的情况下，它是基于问题的线性规划松弛。当多项式时间可计算界，如线性规划界被用来证明强性能保证时，这对于使用穷举搜索解决问题到最优的实践者也有影响，因为强界在快速修剪搜索空间是有用的。该提议的目标是研究当前近似算法知识状态中的一些异常，因为在其他科学领域，对异常的考虑会最快地带来新的进展。一些已知的近似算法使用不是多项式时间可计算的界量；或者，即使是多项式时间可计算的，也很难证明先验地是所考虑问题的界。研究中包括能够满足有限客户需求的设施选址问题(有能力的设施选址问题)，低成本网络的设计问题(斯坦纳树问题)，以及使车辆到达客户的平均时间最小化的车辆路线问题(最小延迟问题)。这项研究的目标是证明这些算法可以用多项式时间可计算的界限来重述，并且尽可能经常地，涉及线性规划松弛的界限。智力优势：可能需要重大的方法论创新来解决这些问题。此外，PI希望通过这项研究找到更简单、更好、更通用、更实用的近似算法。此外，如果这些问题中的一些问题能够找到多项式时间可计算界，将导致更好的穷举搜索算法来寻找这些问题的最优解。PI是近似算法领域的领导者之一，在寻找新方法和改进算法方面有着广泛的记录。广泛的影响：PI将在更广泛的组合优化领域培训研究生研究人员，并在算法领域进行原创研究。由于该提案的目标之一是简化现有成果，因此通过会议和期刊出版物广泛传播研究成果应能增进对这一领域的了解。潜在地，这项研究的结果将是PI在几个场合教授的关于近似算法的研究生班的一部分；这门课以前版本的笔记是公开的，并得到了广泛的应用。最后，由于许多需要考虑的问题具有实际意义，改进的边界将影响实际中使用的启发式和精确优化技术。

Many problems in combinatorial optimization are NP-hard, and unlikely to have efficient algorithms to find the optimal solution. These include multitudes of problems that arise in practice in industry, including locating facilities to service customer demands, scheduling service personnel to make onsite repairs, dispatching vehicles, constructing low-cost networks with specific connectivity properties, routing wires on chips, and many, many others. The typical approaches for solving these problems are to design some heuristic that in practice provides solutions that are good enough, or, if enough time and resources are available and an optimal solution is sufficiently valuable, to designan exhaustive search algorithm to find the optimal solution.In order to mathematically ground the study of heuristics, computer scientists have considered approximation algorithms. These are efficient, polynomial-time algorithms that produce solutions that are provably close in value to the optimal solution. In particular, an _-approximation algorithm produces a solution whose value is within a factor of _ of the value of an optimal solution. The parameter _ is sometimes called the performance guarantee of the algorithm. To prove that the algorithm produces a near-optimal solution, a bound on the optimal value must be used. This bound is often a quantity that can be computed efficiently on its own, and in many interesting cases is based on a linear programming relaxation of the problem. When a polynomial-time computable bound, such as a linear programming bound, is used to prove a strong performance guarantee, this also has implications for practitioners who solve problems to optimality using exhaustive search, since a strong bound is useful in quickly pruning the search space.The goal of the proposal is to study some anomalies in the current state of knowledge of approximation algorithms, since as in other areas of science, consideration of anomalies leads most quickly to new advances. Several known approximation algorithms use as their bound quantities that are not polynomial-time computable; or, even if polynomial-time computable, are difficult to show apriori are bounds on the problem being considered. Included in the study are problems of locating facilities that can serve a bounded amount of customer demand (the capacitated facility location problem), designing low-cost networks (the Steiner tree problem), and the routing of vehicles to minimize the average time at which a vehicle arrives at a customer (the minimumlatency problem). The goal of the research is to show that these algorithms can be restated in terms of polynomial-time computable bounds, and, as often as possible, bounds involving linear programming relaxations.Intellectual merit: Significant methodological innovations will likely be needed to resolvethese issues. Additionally, the PI expects to find simpler, better, more general, and more practical approximation algorithms as a result of this research. Furthermore, if polynomial-time computable bounds can be found for some of these problems, it will lead to better exhaustive search algorithms for finding the optimal solution for these problems. The PI is one of the leaders in the field of approximation algorithms and has an extensive track record of finding new methods and improved algorithms.Broader impact: The PI will train of graduate researchers in the broader area of combinatorial optimization and in conducting original research in the area of algorithms. Since one of the goals of the proposal is the simplification of current results, the broad dissemination of the results of the research through conference and journal publication should increase understanding in the area. Potentially the results of the research will be part of a graduate class that the PI has taught on several occasions on the subject of approximation algorithms; notes from previous versions of the class are publically available and have been widely used. Finally, since many of the problems to be considered have practical importance, the improved bounds developed will affect the heuristics and exact optimization techniques used in practice.