Nearly Optimal Solutions for Stochastic Optimization Problems

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

This grant provides funding for the development of optimization tools and data structures for a wide class of deterministic and stochastic optimization problems. The purpose of the tools is to aid in the development and automated analysis of approximation algorithms, especially approximation algorithms for stochastic optimization problems. The research will focus on Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic dynamic programs. These algorithms guarantee obtaining a solution that is within any specified small error, and where the running time is polynomial in the size of the problem and the inverse of the error. Within the class of approximation algorithms, FPTASs offer the best tradeoffs of guaranteed accuracy versus computational time. In order to develop efficient FPTASs, the research will develop a collection of objects for representing and manipulating approximated functions, as well as a library of algorithms for these objects that can readily be used by other researchers.If successful, the project will lead to improved algorithms for stochastic optimization problems that arise in several different fields of study including: supply chain management, economics, scheduling and mathematical finance. The research will develop efficient algorithms for fundamental problems in these fields such as single-item inventory control, capital budgeting, dynamic capacity expansion, time-cost tradeoff machine scheduling, batch disposal, and mutual fund cash management. Subsequently, the efficient approaches for the fundamental problems can be used as subroutines in more complex and realistic problems in these fields. The proposed work will also lead to new data structures and data objects that will facilitate the development and analysis of approximation algorithms that arise in these and other fields.