Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses

DOI10.1016/0377-2217(84)90053-5zbMath0532.90075OpenAlexW2055037276WikidataQ57401633 ScholiaQ57401633MaRDI QIDQ789319

M. R. B. Clarke, Alan M. Frieze

Publication date: 1984

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(84)90053-5

zbMATH Keywords

asymptotic behaviourprobabilistic analysispolynomial approximation schemedual simplex algorithmepsilon-approximation algorithmm-dimensional 0- 1 knapsack problemtight bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items (50)

Multistage knapsack ⋮ An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem ⋮ The growth of multi-constraint random knapsack with various right-hand sides of the constraints ⋮ Approximation algorithms for the capacitated plant allocation problem ⋮ Shrinking maxima, decreasing costs: new online packing and covering problems ⋮ Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms ⋮ A PTAS for capacitated sum-of-ratios optimization ⋮ Polynomial time approximation schemes for class-constrained packing problems ⋮ A simulated annealing approach to the multiconstraint zero-one knapsack problem ⋮ Envy-free pricing with general supply constraints for unit demand consumers ⋮ Capacity Constraints Across Nests in Assortment Optimization Under the Nested Logit Model ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ The growth of multi-constraint random knapsacks with large right-hand sides of the constraints ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Technical Note—Capacitated Assortment Optimization: Hardness and Approximation ⋮ An improved binary search algorithm for the Multiple-Choice Knapsack Problem ⋮ Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints ⋮ An approximation scheme for a bilevel knapsack problem ⋮ Approximate strong separation with application in fractional graph coloring and preemptive scheduling. ⋮ Approximation schemes for generalized two-dimensional vector packing with application to data placement ⋮ Vector bin packing with multiple-choice ⋮ Tightening simple mixed-integer sets with guaranteed bounds ⋮ A probabilistic analysis of the multiknapsack value function ⋮ A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem ⋮ On the growth of random knapsacks ⋮ The growth of m-constraint random knapsacks ⋮ Scheduling split intervals with non-uniform demands ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ Approximation schemes for deal splitting and covering integer programs with multiplicity constraints ⋮ Distributed approximation of \(k\)-service assignment ⋮ A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem ⋮ Unnamed Item ⋮ Connectivity interdiction ⋮ A binary differential search algorithm for the 0-1 multidimensional knapsack problem ⋮ The preemptive resource allocation problem ⋮ A \(K\)-means supported reinforcement learning framework to multi-dimensional knapsack ⋮ Approximation algorithms for the MAXSPACE advertisement problem ⋮ Expectation analysis for bounding solutions of the 0-1 knapsack problem ⋮ Improved approximation for two-dimensional vector multiple knapsack ⋮ A class of generalized greedy algorithms for the multi-knapsack problem ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ Select and permute: an improved online framework for scheduling to minimize weighted completion time ⋮ A PTAS for a class of binary non-linear programs with low-rank functions ⋮ The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem ⋮ There is no EPTAS for two-dimensional knapsack ⋮ Approximation algorithms for knapsack problems with cardinality constraints ⋮ Random sequencing jobs with deadlines problem: Growth of the optimal solution values ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• Approximate algorithms for some generalized knapsack problems
• Khachiyan’s algorithm for linear programming
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• `` Strong NP-Completeness Results
• A Stability Concept For Zero-One Knapsack Problems And Approximation Algorithms

This page was built for publication: Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses