414
views
0
recommends
+1 Recommend
1 collections
    0
    shares

      One-Click Submission System Now Available for SO Preprints, learn more on how this works in our blog post and don't forget to check the video, too!

      scite_
      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
      combinatorics, knapsack, stochastics, combinatorial optimization
      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.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 .

            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,knapsack,stochastics,combinatorial optimization

            Comments

            Comment on this article