Approximation algorithms for discrete stochastic and deterministic optimization problems

摘要美国国家科学基金会授予0635121--离散随机和确定性优化问题的近似算法David B.Shmoys智力价值--对于工业中使用优化算法的大多数应用来说，输入数据实际上是未知的。这可能是因为数据是以测量为基础的，而测量是由于噪声造成的估计，或者因为只有对未来数据的预测可用。随机优化模型将这种不确定性作为输入的一部分，比确定性模型更难求解。这项研究研究了计算随机优化问题可证近优解的算法；相比之下，传统方法大多显示出收敛结果，而不能保证有效地产生近优解。更广泛的影响-找到良好的方法，在物流规划中获得新的效率，对美国整体经济非常重要。这项研究开发了新的算法技术来做到这一点。通过研究简化模型，本研究设计了算法范例，然后可以应用于更具体的应用，从而为行业提供更好的解决方案。此外，重要的是美国劳动力拥有足够的专业知识来应对下个世纪的技术挑战，通过将这项研究与研究生和本科生的培训相结合，这项工作有助于满足保持美国经济竞争力的需要。这项研究解决了一些具体的离散随机优化问题，主要集中在来自物流的问题：路线、调度、库存管理和网络设计。这项研究的重点是一个“黑箱”，它通过多项式独立于基础分布的样本来指定概率输入；当一个人可以访问历史数据时，这一点很重要。本文研究了随机TSP、最大割数和单机排序问题，可生存网络设计和最大作业选择问题的两阶段带资源模型，以及库存控制、期权定价和AdWords竞价的多阶段随机模型。本研究还研究了确定性非对称TSP问题、装箱问题和有能力的设施选址问题。

Abstract for NSF Grant 0635121 - Approximation algorithms for discrete stochastic and deterministic optimization problemsDavid B. ShmoysIntellectual Merit - For most applications in which optimization algorithms are employed in industry, the input data is actually not known. This might be because the data is based on measurements, which are estimates due to noise, or because only a forecast of future data is available. Stochastic optimization models incorporate this uncertainty as part of the input, and are harder to solve than their deterministic counterparts. This research investigates algorithms that compute provably near-optimal solutions for stochastic optimization problems; in contrast, traditional approaches mostly show convergence results without guarantees to efficiently produce near-optimal solutions. Broader Impact - Finding good approaches to gain new efficiencies in logistical planning is important for the overall US economy. This research develops new algorithmic techniques to do this. By studying simplified models, this research devises algorithmic paradigms that can then be applied in more concrete applications, thereby providing industry with better solutions. Furthermore, it is important that the US workforce has sufficient expertise to meet the technological challenges of the coming century, and by integrating this research with the training of both graduate and undergraduate students, this work helps to meet this need in maintaining the economic competitiveness of the US.This research addresses a number of specific discrete stochastic optimization problems, focusing primarily on problems from logistics: routing, scheduling, inventory management and network design. This research focuses on a "black box" that specifies the probabilistic input by means of polynomial independent samples from the underlying distribution; this is important when one has access to historical data. This work studies the stochastic TSP, max cut, and single-machine scheduling problems; 2-stage with recourse models of the survivable network design and maximum job selection problems, and multistage stochastic models from inventory control, options pricing, and AdWords bidding. This research also studies the deterministic asymmetric TSP, bin-packing, and capacitated facility-location problems.