Fully Polynomial Time Approximation Schemes for Robust Multistage Decision Making
针对预算不确定集下的可调鲁棒多阶段决策问题，设计了全多项式时间近似方案（FPTAS），并应用于有序背包、单物品库存控制和单物品批量调度三个运筹问题，首次为这些问题及一般可调鲁棒多阶段决策提供了FPTAS。
We design a framework to obtain Fully Polynomial Time Approximation Schemes (FPTASes) for adjustable robust multistage decision making under the budgeted uncertainty sets introduced by Bertsimas and Sim. We apply this framework to the robust counterpart of three problems coming from operations research: (i) ordered knapsack, (ii) single-item inventory control, and (iii) single-item batch dispatch. Our work gives the first FPTAS for these problems, and for adjustable robust multistage decision making in general. The proposed approximation schemes are constructed with the technique of K-approximation sets and functions, relying on careful robust dynamic programming formulations for a master problem (corresponding to the decision maker) and for an adversary problem (corresponding to nature, which chooses bad realizations of uncertainty for the decision maker). The resulting algorithms are short and simple, requiring just a few concise subroutines. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was supported in part by the United States-Israel Binational Science foundation [Grant 2018095). N. Halman was also supported in part by the Israel Science Foundation [Grants 399/17 and 1074/21].