CAREER: Approximation Algorithms for Optimization under Uncertainty

点击翻译按钮获取中文摘要

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.