article

On rates of convergence and asymptotic normality in the multiknapsack problem

Authors:

Sara Geer,

Leen StougieAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 51, Issue 1-3

Pages 349 - 358

Published: 01 July 1991 Publication History

Abstract

In Meanti et al. (1990) an almost sure asymptotic characterization has been derived for the optimal solution value as function of the knapsack capacities, when the profit and requirement coefficients of items to be selected from are random variables. In this paper we establish a rate of convergence for this process using results from the theory of empirical processes.

References

[1]

K.S. Alexander, "Probability inequalities for empirical processes and a law of the iterated logarithm," Annals of Probability 12 (1984) 1041-1067.

Crossref

Google Scholar

[2]

R.M. Dudley, "A course on empirical processes," Lecture Notes in Mathematics (Lectures given at Ecole d'Eté de Probabilités de St. Flour 1982) (Springer, Berlin, 1984) pp. 1-142.

Google Scholar

[3]

E. Giné and J. Zinn, "On the central limit theorem for empirical process," Annals of Probability 12 (1984) 929-989.

Crossref

Google Scholar

[4]

A. Marchetti Spaccamela, W.T. Rhee, L. Stougie and S.A. van de Geer, "A probabilistic value analysis of the minimum weighted flowtime scheduling problem," Operations Research Letters 11 (1992), to appear.

Digital Library

Google Scholar

[5]

M. Meanti, A.H.G. Rinnooy Kan, L. Stougie and C. Vercellis, "A probabilistic analysis of the multiknapsack value function," Mathematical Programming 46 (1990) 237-247.

Digital Library

Google Scholar

[6]

N. Piersma, "Empirical process theory and combinatorial optimization: a survey," Thesis, University of Amsterdam (Amsterdam, 1987).

Google Scholar

[7]

D. Pollard, Convergence of Stochastic Processes (Springer, New York, 1984).

Google Scholar

[8]

D. Pollard, "New ways to prove central limit theorems," Econometric Theory 1 (1985) 295-314.

Crossref

Google Scholar

[9]

W.T. Rhee and M. Talagrand, "Exact bounds for the stochastic upward matching problem," Transactions of the American Mathematical Society 307 (1988) 109-125.

Crossref

Google Scholar

[10]

W.T. Rhee and M. Talagrand, "A concentration inequality for the k-median problem," Mathematics of Operations Research 14 (1989) 189-202.

Digital Library

Google Scholar

[11]

A.H.G. Rinnooy Kan, L. Stougie and C. Vercellis, "A class of generalized greedy algorithms for the multiknapsack problem," to appear in: Discrete Applied Mathematics (1992).

Digital Library

Google Scholar

[12]

V.N. Vapnik and Y.A. Chervonenkis, "On the uniform convergence of relative frequencies of events to their probabilities," Theory of Probability and its Applications 16 (1971) 264-280.

Crossref

Google Scholar

Cited By

View all

Pflug GRuszczyñski ASchultz R(1998)On the Glivenko-Cantelli Problem in Stochastic ProgrammingMathematics of Operations Research10.5555/2778229.277823923:1(204-220)Online publication date: 1-Feb-1998
https://dl.acm.org/doi/10.5555/2778229.2778239
Lueker GClarkson K(1995)Average-case analysis of off-line and on-line knapsack problemsProceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/313651.313692(179-188)Online publication date: 22-Jan-1995
https://dl.acm.org/doi/10.5555/313651.313692
Averbakh I(1994)Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithmsMathematical Programming: Series A and B10.1007/BF0158170065:1-3(311-330)Online publication date: 1-Feb-1994
https://dl.acm.org/doi/10.1007/BF01581700

Index Terms

On rates of convergence and asymptotic normality in the multiknapsack problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
  2. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

On the Rates of Asymptotic Normality for Bernstein Polynomial Estimators in a Triangular Array
Abstract
It is well known that the empirical distribution function has superior properties as an estimator of the underlying distribution function F. However, considering its jump discontinuities, the estimator is limited when F is continuous. Mixtures of ...
Several improved asymptotic normality criteria and their applications to graph polynomials
Abstract
As widely regarded, one of the most classical and remarkable tools to measure the asymptotic normality of combinatorial statistics is due to Harper's real-rooted method proposed in 1967. However, this classical theorem exists some ...
Multivariate versions of Bartlett's formula

This paper quantifies the form of the asymptotic covariance matrix of the sample autocovariances in a multivariate stationary time series-the classic Bartlett formula. Such quantification is useful in many statistical inferences involving ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 51, Issue 1-3

July 1991

408 pages

ISSN:0025-5610

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 July 1991

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pflug GRuszczyñski ASchultz R(1998)On the Glivenko-Cantelli Problem in Stochastic ProgrammingMathematics of Operations Research10.5555/2778229.277823923:1(204-220)Online publication date: 1-Feb-1998
https://dl.acm.org/doi/10.5555/2778229.2778239
Lueker GClarkson K(1995)Average-case analysis of off-line and on-line knapsack problemsProceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/313651.313692(179-188)Online publication date: 22-Jan-1995
https://dl.acm.org/doi/10.5555/313651.313692
Averbakh I(1994)Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithmsMathematical Programming: Series A and B10.1007/BF0158170065:1-3(311-330)Online publication date: 1-Feb-1994
https://dl.acm.org/doi/10.1007/BF01581700

Abstract

References

Cited By

Index Terms

Recommendations

On the Rates of Asymptotic Normality for Bernstein Polynomial Estimators in a Triangular Array

Several improved asymptotic normality criteria and their applications to graph polynomials

Multivariate versions of Bartlett's formula

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations