CAREER: Approximation Algorithms for Optimization under Uncertainty

职业：不确定性下优化的近似算法

• 批准号: 0643763
• 负责人: Shuchi Chawla
• 金额: $ 40万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-03-15 至 2013-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0643763&HistoricalAwards=false
• 关键词: CAREER; Approximation; Algorithms; Optimization; under

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.

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