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

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 behaviour probabilistic analysis polynomial approximation scheme dual simplex algorithm epsilon-approximation algorithm m-dimensional 0- 1 knapsack problem tight bounds

Mathematics Subject Classification ID

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

Related Items

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, 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