212
views
0
recommends
+1 Recommend
1 collections
0
shares
Version and Review History

• Record: found
• Abstract: found
• Article: found
Is Open Access

New Bounds for the Stochastic Knapsack Problem

Preprint
In review
research-article
1 ,
ScienceOpen Preprints
ScienceOpen
Bookmark

Abstract

The knapsack problem is a problem in combinatorial optimization that seeks to maximize the objective function $$\sum_{i = 1}^{n} v_ix_i$$ subject to the constraints $$\sum_{i = 1}^{n} w_ix_i \leq W$$ and $$x_i \in \{0, 1\}$$, where $$\mathbf{x}, \mathbf{v} \in \mathbb{R}^{n}$$ and $$W$$ are provided. We consider the stochastic variant of this problem in which $$\mathbf{v}$$ remains deterministic, but $$\mathbf{x}$$is an $$n$$-dimensional vector drawn uniformly at random from $$[0, 1]^{n}$$. We establish a sufficient condition under which the summation-bound condition is almost surely satisfied. Furthermore, we discuss the implications of this result on the deterministic problem.

Author and article information

Journal
ScienceOpen Preprints
ScienceOpen
5 June 2020
Affiliations
[1 ] University of Maryland
Article
10.14293/S2199-1006.1.SOR-.PPDDJQL.v2
2c4ea128-b5ae-4406-a3d4-9641561bccfc

This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

All data generated or analysed during this study are included in this published article (and its supplementary information files).
Computer science,Statistics,Mathematics