Expectation analysis for bounding solutions of the 0-1 knapsack problem

DOI10.1007/S40314-024-02938-6MaRDI QIDQ6636466zbMATH OpenFDO

Authors Fernando A. Morales, Jairo A. Martínez

Publication date 12 November 2024

Published in Computational and Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S40314-024-02938-6

zbMATH Keywords

0-1 knapsack problemdiscrete optimizationprobabilistic analysis of algorithms

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Integer programming (90C10)

Recommendations

• Probabilistic Analysis of the Multidimensional Knapsack Problem
• Random knapsack in expected polynomial time
• Random knapsack in expected polynomial time
• scientific article; zbMATH DE number 4057284
• scientific article; zbMATH DE number 3878679

Cites work

• A New Algorithm for the 0-1 Knapsack Problem
• A new class of hard problem instances for the 0-1 knapsack problem
• A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs
• A walk through combinatorics. An introduction to enumeration and graph theory
• Algorithms for the one-dimensional two-stage cutting stock problem
• An Algorithm for Large Zero-One Knapsack Problems
• An expanding-core algorithm for the exact 0-1 knapsack problem
• Analysis of divide-and-conquer strategies for the 0-1 minimization knapsack problem
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.
• Average-case performance of rollout algorithms for knapsack problems
• Computing Partitions with Applications to the Knapsack Problem
• Discrete probability models and methods. Probability on graphs and trees, Markov chains and random fields, entropy and coding
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Dynamic programming on the word RAM
• Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems
• Greedy algorithms for the minimization knapsack problem: average behavior
• Hard Knapsack Problems
• scientific article; zbMATH DE number 5767933 (Why is no real title available?)
• scientific article; zbMATH DE number 4057285 (Why is no real title available?)
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Minimum and worst-case performance ratios of rollout algorithms
• Reducibility among combinatorial problems
• Relaxation analysis for the dynamic knapsack problem with stochastic item sizes
• Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic
• Revisiting \textit{Where are the hard knapsack problems?} via instance space analysis
• Where are the hard knapsack problems?

Cited in

(1)

• An evolutionary algorithm for solving a unique discounted 0-1 knapsack problem in a random type-2 fuzzy environment

This page was built for publication: Expectation analysis for bounding solutions of the 0-1 knapsack problem

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