Blog
About

50
views
1
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      New Bounds for the Stochastic Knapsack Problem

      Preprint
      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

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Author and article information

          Journal
          ScienceOpen Preprints
          ScienceOpen
          5 June 2020
          Affiliations
          [1 ] University of Maryland
          Article
          10.14293/S2199-1006.1.SOR-.PPDDJQL.v1

          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

          combinatorics, ekesh, statistics, math, random, kumar, bounds, stochastic, knapsack, optimization

          Comments

          Comment on this article