CAREER: Approximation Algorithms for Optimization under Uncertainty

实践中出现的大多数优化问题都涉及不确定性：一些感兴趣的参数可能来自未来的过程(例如影响商品需求的市场力量)，或者来自不精确的衡量，或者可能是出于隐私利益而故意“捏造”的。然而，人们通常可以获得关于这些参数的一些有限的分布信息，例如通过过去对相同过程的观测或通过重复测量。如何利用这些有限的信息来找到最有效的优化问题的解决方案？这个问题构成了随机优化的症结所在。最近的理论工作介绍了处理不确定性的新技术，以及暴露了随机优化独有的挑战。这项研究的一个主要重点是进一步发展随机优化问题的可逼近理论。PI将研究调度、机器人运动规划、网络设计和资源分配中的优化问题，重点关注以下问题：(1)如何以及对于什么问题，我们可以将在全信息环境下工作良好的算法转换成在随机环境下工作良好的算法？(2)为了获得良好的逼近，我们需要多少关于输入分布的信息？(3)多阶段随机问题的最优解可以是复杂的指数大小的决策图。对于哪些问题，这种复杂的解可以用简单得多的解来近似？(4)对于哪些多阶段随机问题，本质上很难获得与阶段数无关的近似因子？该项目的另一个重点领域是为在线零售和赞助搜索拍卖等环境中出现的贝叶斯机制设计和定价问题设计近似最优算法。这项研究计划将涉及所有级别的学生，包括旨在对算法进行实验评估的本科生项目。此外，PI计划修改威斯康星大学麦迪逊分校的算法课程，增加与算法实际应用相关的新本科课程内容，以及基于算法博弈论等算法高级应用的新研究生课程。

Most optimization problems arising in practice involve uncertainty: some parameters of interest may arise from a future process (such as market forces affecting the demand for a good), or from an imprecise measurement, or may be ``fudged'' on purpose in the interest of privacy. However, one can usually obtain some limited distributional information about such parameters, such as through past observations of the same process or by repeated measurements. How can this limited information be utilized to find solutions to the optimization problem that mostly work well? This question forms the crux of stochastic optimization. Recent theoretical work has introduced novel techniques for dealing with uncertainty, as well as exposed challenges unique to stochastic optimization. A primary focus of this research is to further this theory of approximability of stochastic optimization problems.The PI will investigate optimization problems arising in scheduling, robot motion planning, network design, and resource allocation, with emphasis on the following issues: (1) How, and for what problems, can we transform algorithms that work well in the full-information setting to those that work well in the stochastic setting?; (2) How much information do we require about input distributions in order to obtain a good approximation?; (3) Optimal solutions to multi-stage stochastic problems can be complex exponential-size decision diagrams. For which problems can such complex solutions be approximated by much simpler ones?; (4) For which multi-stage stochastic problems is it inherently hard to obtain approximation factors independent of the number of stages? Another area of focus for this project is the design of approximately optimal algorithms for Bayesian mechanism design and pricing problems arising in contexts such as online retailing and sponsored search auctions. This research program will involve students at all levels, including undergraduate projects aimed at experimentally evaluating algorithms. In addition, the PI plans to revamp algorithms courses at the University of Wisconsin-Madison, adding new undergraduate course content related to practical applications of algorithms, and new graduate courses based on advanced applications of algorithms such as algorithmic game theory.