Boolean function analysis meets stochastic optimization

An approximation scheme for stochastic knapsack

Anindya De*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

The stochastic knapsack problem is the stochastic variant of the classical knapsack problem in which the algorithm designer is given a a knapsack with a given capacity and a collection of items where each item is associated with a profit and a probability distribution on its size. The goal is to select a subset of items with maximum profit and violate the capacity constraint with probability at most p (referred to as the overow probability). While several approximation algorithms [27, 22, 4, 17, 30] have been developed for this problem, most of these algorithms relax the capacity constraint of the knapsack. In this paper, we design efficient approximation schemes for this problem without relaxing the capacity constraint. (i) Our first result is in the case when item sizes are Bernoulli random variables. In this case, we design a (nearly) fully polynomial time approximation scheme (FPTAS) which only relaxes the overow probability. (ii) Our second result generalizes the first result to the case when all the item sizes are supported on a (common) set of constant size. In this case, we obtain a quasiFPTAS. (iii) Our third result is in the case when item sizes are socalled "hypercontractive" random variables i.e., random variables whose second and fourth moments are within constant factors of each other. In other words, the kurtosis of the random variable is upper bounded by a constant. This class has been widely studied in probability theory and most natural random variables are hypercontractive including well-known families such as Poisson, Gaussian, exponential and Laplace distributions. In this case, we design a polynomial time approximation scheme which relaxes both the overow probability and maximum profit.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages1286-1305
Number of pages20
ISBN (Electronic)9781611975031
DOIs
StatePublished - Jan 1 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
CountryUnited States
CityNew Orleans
Period1/7/181/10/18

Fingerprint

Boolean functions
Knapsack
Stochastic Optimization
Approximation Scheme
Boolean Functions
Random variables
Capacity Constraints
Random variable
Profit
Profitability
Knapsack Problem
Polynomials
Bernoulli Random Variables
Laplace Distribution
Fully Polynomial Time Approximation Scheme
Polynomial Time Approximation Scheme
Kurtosis
Poisson distribution
Approximation algorithms
Probability Theory

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

De, A. (2018). Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack. In A. Czumaj (Ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 (pp. 1286-1305). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611975031.84
De, Anindya. / Boolean function analysis meets stochastic optimization : An approximation scheme for stochastic knapsack. 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. editor / Artur Czumaj. Association for Computing Machinery, 2018. pp. 1286-1305 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{75dc8f60b7b14cb69b7060b72cedff58,
title = "Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack",
abstract = "The stochastic knapsack problem is the stochastic variant of the classical knapsack problem in which the algorithm designer is given a a knapsack with a given capacity and a collection of items where each item is associated with a profit and a probability distribution on its size. The goal is to select a subset of items with maximum profit and violate the capacity constraint with probability at most p (referred to as the overow probability). While several approximation algorithms [27, 22, 4, 17, 30] have been developed for this problem, most of these algorithms relax the capacity constraint of the knapsack. In this paper, we design efficient approximation schemes for this problem without relaxing the capacity constraint. (i) Our first result is in the case when item sizes are Bernoulli random variables. In this case, we design a (nearly) fully polynomial time approximation scheme (FPTAS) which only relaxes the overow probability. (ii) Our second result generalizes the first result to the case when all the item sizes are supported on a (common) set of constant size. In this case, we obtain a quasiFPTAS. (iii) Our third result is in the case when item sizes are socalled {"}hypercontractive{"} random variables i.e., random variables whose second and fourth moments are within constant factors of each other. In other words, the kurtosis of the random variable is upper bounded by a constant. This class has been widely studied in probability theory and most natural random variables are hypercontractive including well-known families such as Poisson, Gaussian, exponential and Laplace distributions. In this case, we design a polynomial time approximation scheme which relaxes both the overow probability and maximum profit.",
author = "Anindya De",
year = "2018",
month = "1",
day = "1",
doi = "10.1137/1.9781611975031.84",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "1286--1305",
editor = "Artur Czumaj",
booktitle = "29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018",

}

De, A 2018, Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack. in A Czumaj (ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 1286-1305, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, United States, 1/7/18. https://doi.org/10.1137/1.9781611975031.84

Boolean function analysis meets stochastic optimization : An approximation scheme for stochastic knapsack. / De, Anindya.

29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. ed. / Artur Czumaj. Association for Computing Machinery, 2018. p. 1286-1305 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Boolean function analysis meets stochastic optimization

T2 - An approximation scheme for stochastic knapsack

AU - De, Anindya

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The stochastic knapsack problem is the stochastic variant of the classical knapsack problem in which the algorithm designer is given a a knapsack with a given capacity and a collection of items where each item is associated with a profit and a probability distribution on its size. The goal is to select a subset of items with maximum profit and violate the capacity constraint with probability at most p (referred to as the overow probability). While several approximation algorithms [27, 22, 4, 17, 30] have been developed for this problem, most of these algorithms relax the capacity constraint of the knapsack. In this paper, we design efficient approximation schemes for this problem without relaxing the capacity constraint. (i) Our first result is in the case when item sizes are Bernoulli random variables. In this case, we design a (nearly) fully polynomial time approximation scheme (FPTAS) which only relaxes the overow probability. (ii) Our second result generalizes the first result to the case when all the item sizes are supported on a (common) set of constant size. In this case, we obtain a quasiFPTAS. (iii) Our third result is in the case when item sizes are socalled "hypercontractive" random variables i.e., random variables whose second and fourth moments are within constant factors of each other. In other words, the kurtosis of the random variable is upper bounded by a constant. This class has been widely studied in probability theory and most natural random variables are hypercontractive including well-known families such as Poisson, Gaussian, exponential and Laplace distributions. In this case, we design a polynomial time approximation scheme which relaxes both the overow probability and maximum profit.

AB - The stochastic knapsack problem is the stochastic variant of the classical knapsack problem in which the algorithm designer is given a a knapsack with a given capacity and a collection of items where each item is associated with a profit and a probability distribution on its size. The goal is to select a subset of items with maximum profit and violate the capacity constraint with probability at most p (referred to as the overow probability). While several approximation algorithms [27, 22, 4, 17, 30] have been developed for this problem, most of these algorithms relax the capacity constraint of the knapsack. In this paper, we design efficient approximation schemes for this problem without relaxing the capacity constraint. (i) Our first result is in the case when item sizes are Bernoulli random variables. In this case, we design a (nearly) fully polynomial time approximation scheme (FPTAS) which only relaxes the overow probability. (ii) Our second result generalizes the first result to the case when all the item sizes are supported on a (common) set of constant size. In this case, we obtain a quasiFPTAS. (iii) Our third result is in the case when item sizes are socalled "hypercontractive" random variables i.e., random variables whose second and fourth moments are within constant factors of each other. In other words, the kurtosis of the random variable is upper bounded by a constant. This class has been widely studied in probability theory and most natural random variables are hypercontractive including well-known families such as Poisson, Gaussian, exponential and Laplace distributions. In this case, we design a polynomial time approximation scheme which relaxes both the overow probability and maximum profit.

UR - http://www.scopus.com/inward/record.url?scp=85045557948&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045557948&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.84

DO - 10.1137/1.9781611975031.84

M3 - Conference contribution

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1286

EP - 1305

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

ER -

De A. Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack. In Czumaj A, editor, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Association for Computing Machinery. 2018. p. 1286-1305. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). https://doi.org/10.1137/1.9781611975031.84