293
views
1
recommends
+1 Recommend
1 collections
    0
    shares
      scite_
      Version and Review History
       
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      New Bounds for the Stochastic Knapsack Problem

      Preprint
      research-article
      This is not the latest version for this article. If you want to read the latest version, click here.
        1 ,
      ScienceOpen Preprints
      ScienceOpen
      combinatorics, optimization, knapsack, stochastic, bounds, random, math, statistics, ekesh, kumar
      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.

            Content

            Author and article information

            Journal
            ScienceOpen Preprints
            ScienceOpen
            5 June 2020
            Affiliations
            [1 ] University of Maryland
            Author information
            https://orcid.org/0000-0003-1811-9184
            Article
            10.14293/S2199-1006.1.SOR-.PPDDJQL.v1
            552e06c4-83b3-4789-8d17-c2ddbb00c484

            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 .

            History
            : 5 June 2020

            All data generated or analysed during this study are included in this published article (and its supplementary information files).
            Computer science,Statistics,Mathematics
            combinatorics,kumar,random,math,statistics,ekesh,optimization,knapsack,stochastic,bounds

            Comments

            Comment on this article