Approximation algorithms for discrete stochastic and deterministic optimization problems

摘要为美国国家科学基金会资助0635121 -近似算法离散随机和确定性优化问题大卫B。ShmoysIntellectual Merit -对于大多数工业中采用优化算法的应用程序，输入数据实际上是未知的。这可能是因为数据是基于测量的，而测量是由于噪声而引起的估计，或者因为只有对未来数据的预测可用。随机优化模型将这种不确定性作为输入的一部分，并且比确定性模型更难求解。本研究调查算法，计算可证明的随机优化问题的接近最优的解决方案，相比之下，传统的方法大多显示收敛的结果，没有保证有效地产生接近最优的解决方案。 更广泛的影响-找到好的方法来获得新的效率，在物流规划是重要的整体美国经济。 这项研究开发了新的算法技术来做到这一点。通过研究简化的模型，本研究设计了算法范例，然后可以应用于更具体的应用程序，从而为行业提供更好的解决方案。 此外，重要的是，美国劳动力有足够的专业知识，以满足未来世纪的技术挑战，并通过将本研究与研究生和本科生的培训，这项工作有助于满足这一需要，在保持美国的经济竞争力。这项研究解决了一些具体的离散随机优化问题，主要集中在物流问题：路由，调度，库存管理和网络设计。这项研究的重点是一个“黑盒子”，指定的概率输入多项式独立的样本从底层分布的方式，这是很重要的，当一个访问历史数据。 本文研究了随机TSP问题、最大割问题和单机调度问题; 2-阶段可生存网络设计和最大作业选择问题的资源模型;以及库存控制、期权定价和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.