TY - GEN
T1 - A PTAS for a class of stochastic dynamic programs
AU - Fu, Hao
AU - Li, Jian
AU - Xu, Pan
N1 - Publisher Copyright:
© Hao Fu, Jian Li, and Pan Xu;.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - We develop a framework for obtaining polynomial time approximation schemes (PTAS) for a class of stochastic dynamic programs. Using our framework, we obtain the first PTAS for the following stochastic combinatorial optimization problems: 1. Probemax [19]: We are given a set of n items, each item i ∈ [n] has a value Xi which is an independent random variable with a known (discrete) distribution πi. We can probe a subset P ⊆ [n] of items sequentially. Each time after probing an item i, we observe its value realization, which follows the distribution πi. We can adaptively probe at most m items and each item can be probed at most once. The reward is the maximum among the m realized values. Our goal is to design an adaptive probing policy such that the expected value of the reward is maximized. To the best of our knowledge, the best known approximation ratio is 1 − 1/e, due to Asadpour et al. [2]. We also obtain PTAS for some generalizations and variants of the problem. 2. Committed Pandora's Box [24, 22]: We are given a set of n boxes. For each box i ∈ [n], the cost ci is deterministic and the value Xi is an independent random variable with a known (discrete) distribution πi. Opening a box i incurs a cost of ci. We can adaptively choose to open the boxes (and observe their values) or stop. We want to maximize the expectation of the realized value of the last opened box minus the total opening cost. 3. Stochastic Target [15]: Given a predetermined target T and n items, we can adaptively insert the items into a knapsack and insert at most m items. Each item i has a value Xi which is an independent random variable with a known (discrete) distribution. Our goal is to design an adaptive policy such that the probability of the total values of all items inserted being larger than or equal to T is maximized. We provide the first bi-criteria PTAS for the problem. 4. Stochastic Blackjack Knapsack [16]: We are given a knapsack of capacity C and probability distributions of n independent random variables Xi. Each item i ∈ [n] has a size Xi and a profit pi. We can adaptively insert the items into a knapsack, as long as the capacity constraint is not violated. We want to maximize the expected total profit of all inserted items. If the capacity constraint is violated, we lose all the profit. We provide the first bi-criteria PTAS for the problem.
AB - We develop a framework for obtaining polynomial time approximation schemes (PTAS) for a class of stochastic dynamic programs. Using our framework, we obtain the first PTAS for the following stochastic combinatorial optimization problems: 1. Probemax [19]: We are given a set of n items, each item i ∈ [n] has a value Xi which is an independent random variable with a known (discrete) distribution πi. We can probe a subset P ⊆ [n] of items sequentially. Each time after probing an item i, we observe its value realization, which follows the distribution πi. We can adaptively probe at most m items and each item can be probed at most once. The reward is the maximum among the m realized values. Our goal is to design an adaptive probing policy such that the expected value of the reward is maximized. To the best of our knowledge, the best known approximation ratio is 1 − 1/e, due to Asadpour et al. [2]. We also obtain PTAS for some generalizations and variants of the problem. 2. Committed Pandora's Box [24, 22]: We are given a set of n boxes. For each box i ∈ [n], the cost ci is deterministic and the value Xi is an independent random variable with a known (discrete) distribution πi. Opening a box i incurs a cost of ci. We can adaptively choose to open the boxes (and observe their values) or stop. We want to maximize the expectation of the realized value of the last opened box minus the total opening cost. 3. Stochastic Target [15]: Given a predetermined target T and n items, we can adaptively insert the items into a knapsack and insert at most m items. Each item i has a value Xi which is an independent random variable with a known (discrete) distribution. Our goal is to design an adaptive policy such that the probability of the total values of all items inserted being larger than or equal to T is maximized. We provide the first bi-criteria PTAS for the problem. 4. Stochastic Blackjack Knapsack [16]: We are given a knapsack of capacity C and probability distributions of n independent random variables Xi. Each item i ∈ [n] has a size Xi and a profit pi. We can adaptively insert the items into a knapsack, as long as the capacity constraint is not violated. We want to maximize the expected total profit of all inserted items. If the capacity constraint is violated, we lose all the profit. We provide the first bi-criteria PTAS for the problem.
KW - Approximation algorithm
KW - Block policy
KW - Dynamic program
KW - Markov decision process
KW - Stochastic optimization
UR - http://www.scopus.com/inward/record.url?scp=85049805646&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049805646&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2018.56
DO - 10.4230/LIPIcs.ICALP.2018.56
M3 - Conference contribution
AN - SCOPUS:85049805646
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
A2 - Kaklamanis, Christos
A2 - Marx, Daniel
A2 - Chatzigiannakis, Ioannis
A2 - Sannella, Donald
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Y2 - 9 July 2018 through 13 July 2018
ER -