Stochastic on-line knapsack problems

DOI10.1007/BF01585758MaRDI QIDQ1804369zbMATH OpenOpenAlexFDO

Authors Alberto Marchetti-Spaccamela, C. 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

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

Recommendations

• scientific article; zbMATH DE number 4047112
• Average-Case Analysis of Off-Line and On-Line Knapsack Problems
• Publication:4886047

Cites work

• scientific article; zbMATH DE number 3945879 (Why is no real title available?)
• scientific article; zbMATH DE number 4053339 (Why is no real title available?)
• scientific article; zbMATH DE number 4057285 (Why is no real title available?)
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3538576 (Why is no real title available?)
• A probabilistic analysis of the multiknapsack value function
• A provably efficient algorithm for dynamic storage allocation
• Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
• Approximation algorithms for combinatorial problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Multi-constrained matroidal knapsack problems
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• Probability Inequalities for Sums of Bounded Random Variables
• The average-case analysis of some on-line algorithms for bin packing

Cited in

(38)

• Online knapsack with resource augmentation
• Probabilistic Model of Ant Colony Optimization for Multiple Knapsack Problem
• Packing a knapsack of unknown capacity
• The advice complexity of a class of hard online problems
• Online knapsack with removal and recourse
• Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm
• Online Knapsack Problem Under Concave Functions
• Knapsack secretary through boosting
• scientific article; zbMATH DE number 910873 (Why is no real title available?)
• Fractionally subadditive maximization under an incremental knapsack constraint
• Improved online algorithm for fractional knapsack in the random order model
• The online knapsack problem with incremental capacity
• The online knapsack problem: advice and randomization
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• Online unit profit knapsack with predictions
• On two-stage stochastic knapsack problems
• 2D knapsack: packing squares
• Online budgeted maximum coverage
• Online removable knapsack problem under convex function
• Online knapsack problem under concave functions
• Average-case performance of rollout algorithms for knapsack problems
• A class of generalized greedy algorithms for the multi-knapsack problem
• Online generalized assignment problem with historical information
• Online minimization knapsack problem
• 2D knapsack: packing squares
• Online knapsack of unknown capacity. How to optimize energy consumption in smartphones
• Improved online algorithms for knapsack and GAP in the random order model
• Improving LTL truck load utilization on line
• Randomized algorithms for online knapsack problems
• Online removable knapsack with limited cuts
• Online knapsack revisited
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• Online unweighted knapsack problem with removal cost
• Algorithms for randomized time-varying knapsack problems
• On the sum minimization version of the online bin covering problem
• A theory of auto-scaling for resource reservation in cloud services
• Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
• scientific article; zbMATH DE number 4047112 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1804369)