AF: Small: AAdvances in the Design of Approximation Algorithms for Optimization Problems

对于工业中使用优化算法的大多数应用，特别是来自物流、供应链管理、路线和网络设计的问题，计算问题是棘手的--输入数据的大小有严格的限制，可以快速可靠地解决到最优。我们将专注于在算法设计中开发新的算法技术，以产生这些关键问题的良好解决方案。这些算法的理论基础是，它们拥有性能保证，确保计算出的解几乎是最优的；例如，该项目旨在设计有效的算法来找到其成本不超过最小可能值的指定百分比的解。该项目还考虑了随机优化问题，其中输入由输入的概率分布组成，从而产生比输入确定的情况下更困难的问题。这个项目旨在为许多理论模型提供强有力的算法保证，这些模型包括容量受限的设施选址问题，它出现在许多工业环境中，从分配网络中的仓库位置到高带宽网络中的枢纽位置的选择；广义分配问题，它在不同的环境中有一系列的负载平衡应用；瓶颈非对称旅行商问题(TSP)，它出现在化工加工厂的调度(技术上称为无等待流水作业调度环境)中，以及更多研究的最小和变量；以及几个随机优化模型，其中一个来自医疗运输飞机的自适应路线选择。找到良好的方法来获得物流规划的新效率是一个对美国整体经济很重要的问题，这也是这个项目的长期目标。我们的观点是，对简化模型的研究将产生可应用于具有行业规模的数据和复杂性的现实环境的算法范例。证明有关解决方案质量的强大定理所需的洞察力转化为算法原则，这反过来又导致算法在行业需要解决的问题上发挥很好的作用。通过培训该领域的研究生，该项目还将有助于确保美国劳动力拥有足够的专业知识，以应对下个世纪在后勤支持领域的技术挑战的重要努力。

For most applications in which optimization algorithms are used in industry, and in particular problems from logistics, supply-chain management, routing, and network design, the computational problems are intractable -- there are severe restrictions on the size of input data that can be quickly and reliably solved to optimality. We will focus on the development of new algorithmic techniques in the design of algorithms to produce good solutions for these critical problems. The theoretical foundation of these algorithms is that they possess a performance guarantee that assures that the solutions computed are nearly optimal; for example, the project aims to devise efficient algorithms to find solutions for which the cost is no more than a specified percentage more than the minimum possible. The project also considers stochastic optimization problems, where the input consists of a probability distribution over inputs, thereby giving rise to even more difficult problems than if the input is known with certainty. We will focus on problem formulations and approaches that allow us to model the requisite probability distributions using historical data archives.This project aims to provide algorithms with strong guarantees for a number of theoretical models including the capacitated facility location problem, which arises in many industrial contexts from the positioning of warehouses in a distribution network to the choice of hub placements in high-bandwidth networks; the generalized assignment problem, which has a range of workload-balancing applications in heterogeneous environments; the bottleneck asymmetric traveling salesman problem (TSP), which arises in scheduling of chemical processing plants (known technically as a no-wait flowshop scheduling environment), as well as the more often studied minimum-sum variant; and several stochastic optimization models including one arising from the adaptive routing of medical transport planes.Finding good approaches to gain new efficiencies in logistical planning is an issue that is important for the overall US economy, and this is a long-term goal of this project. Our viewpoint is that the study of simplified models will yield algorithmic paradigms that can be applied to realistic settings with industry-scale data and complexities. The insight needed to prove strong theorems about the quality of the solutions found translates into algorithmic principles, which in turn leads to algorithms that work well on the problems that industry needs to solve. By training graduate students in this area, this project will also contribute to the important effort to ensure that the US workforce has sufficient expertise to meet the technological challenges of the coming century in the area of logistics support.