Shabtai, Galia ;
Raz, Danny ;
Shavitt, Yuval
A Relaxed FPTAS for ChanceConstrained Knapsack
Abstract
The stochastic knapsack problem is a stochastic version of the well known deterministic knapsack problem, in which some of the input values are random variables. There are several variants of the stochastic problem. In this paper we concentrate on the chanceconstrained variant, where item values are deterministic and item sizes are stochastic. The goal is to find a maximum value allocation subject to the constraint that the overflow probability is at most a given value. Previous work showed a PTAS for the problem for various distributions (Poisson, Exponential, Bernoulli and Normal). Some strictly respect the constraint and some relax the constraint by a factor of (1+epsilon). All algorithms use Omega(n^{1/epsilon}) time. A very recent work showed a "almost FPTAS" algorithm for Bernoulli distributions with O(poly(n) * quasipoly(1/epsilon)) time.
In this paper we present a FPTAS for normal distributions with a solution that satisfies the chance constraint in a relaxed sense. The normal distribution is particularly important, because by the BerryEsseen theorem, an algorithm solving the normal distribution also solves, under mild conditions, arbitrary independent distributions. To the best of our knowledge, this is the first (relaxed or nonrelaxed) FPTAS for the problem. In fact, our algorithm runs in poly(n/epsilon) time. We achieve the FPTAS by a delicate combination of previous techniques plus a new alternative solution to the nonheavy elements that is based on a nonconvex program with a simple structure and an O(n^2 log {n/epsilon}) running time. We believe this part is also interesting on its own right.
BibTeX  Entry
@InProceedings{shabtai_et_al:LIPIcs:2018:10020,
author = {Galia Shabtai and Danny Raz and Yuval Shavitt},
title = {{A Relaxed FPTAS for ChanceConstrained Knapsack}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {72:172:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10020},
URN = {urn:nbn:de:0030drops100201},
doi = {10.4230/LIPIcs.ISAAC.2018.72},
annote = {Keywords: Stochastic knapsack, Chance constraint, Approximation algorithms, Combinatorial optimization}
}
2018
Keywords: 

Stochastic knapsack, Chance constraint, Approximation algorithms, Combinatorial optimization 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

2018 