Stochastic on-line knapsack problems

DOI10.1007/BF01585758zbMath0832.90083OpenAlexW1970970009MaRDI QIDQ1804369

Alberto Marchetti-Spaccamela, Carlo Vercellis

Publication date: 5 March 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585758

zbMATH Keywords

on-line algorithmsstochastic knapsack problems

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Stochastic programming (90C15) Boolean programming (90C09)

Related Items (33)

Packing a Knapsack of Unknown Capacity ⋮ The online knapsack problem with incremental capacity ⋮ A Theory of Auto-Scaling for Resource Reservation in Cloud Services ⋮ Online knapsack of unknown capacity. How to optimize energy consumption in smartphones ⋮ Online knapsack with resource augmentation ⋮ 2D knapsack: packing squares ⋮ Online removable knapsack with limited cuts ⋮ Online minimization knapsack problem ⋮ The advice complexity of a class of hard online problems ⋮ Knapsack secretary through boosting ⋮ Online knapsack with removal and recourse ⋮ Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ⋮ Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ The online knapsack problem: advice and randomization ⋮ On two-stage stochastic knapsack problems ⋮ Online removable knapsack problem under convex function ⋮ Randomized algorithms for online knapsack problems ⋮ Online Knapsack Problem Under Concave Functions ⋮ Online unweighted knapsack problem with removal cost ⋮ Improved Online Algorithms for Knapsack and GAP in the Random Order Model ⋮ Online budgeted maximum coverage ⋮ 2D Knapsack: Packing Squares ⋮ Improving LTL truck load utilization on line ⋮ On the sum minimization version of the online bin covering problem ⋮ Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm ⋮ Improved online algorithms for Knapsack and GAP in the random order model ⋮ Probabilistic Model of Ant Colony Optimization for Multiple Knapsack Problem ⋮ A class of generalized greedy algorithms for the multi-knapsack problem ⋮ Online knapsack problem under concave functions ⋮ Improved online algorithm for fractional knapsack in the random order model ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ Online generalized assignment problem with historical information ⋮ Online knapsack revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A provably efficient algorithm for dynamic storage allocation
• A probabilistic analysis of the multiknapsack value function
• The average-case analysis of some on-line algorithms for bin packing
• Approximation algorithms for combinatorial problems
• Multi-constrained matroidal knapsack problems
• Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: Stochastic on-line knapsack problems