License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.72
URN: urn:nbn:de:0030-drops-100201
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10020/
Shabtai, Galia ;
Raz, Danny ;
Shavitt, Yuval
A Relaxed FPTAS for Chance-Constrained 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 chance-constrained 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 Berry-Esseen 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 non-relaxed) 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 non-heavy elements that is based on a non-convex 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 Chance-Constrained Knapsack}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {72:1--72:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10020},
URN = {urn:nbn:de:0030-drops-100201},
doi = {10.4230/LIPIcs.ISAAC.2018.72},
annote = {Keywords: Stochastic knapsack, Chance constraint, Approximation algorithms, Combinatorial optimization}
}
|
Keywords: |
|
Stochastic knapsack, Chance constraint, Approximation algorithms, Combinatorial optimization |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
