Approximate Algorithms for the 0/1 Knapsack Problem
From MaRDI portal
Publication:4136930
DOI10.1145/321864.321873zbMath0362.90066WikidataQ97016584 ScholiaQ97016584MaRDI QIDQ4136930
Publication date: 1975
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321864.321873
65K05: Numerical mathematical programming methods
90C10: Integer programming
68W99: Algorithms in computer science
Related Items
APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS, Principles and applications of continual computation, Approximate solution of NP optimization problems, The zone hopping problem, Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses, Data dependent worst case bound improving techniques in zero-one programming, The multidimensional 0-1 knapsack problem -- bounds and computational aspects, Single-vendor multi-buyer inventory coordination under private information, A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles, Nonconvex piecewise linear knapsack problems, Playing monotone games to understand learning behaviors, Market-based pricing in grids: on strategic manipulation and computational cost, An asymptotically exact polynomial algorithm for equipartition problems, On different approximation criteria for subset product problems, Parallel generation of permutations and combinations, A new enumeration scheme for the knapsack problem, The knapsack problem with generalized upper bounds, Discrete extremal problems, A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem, Approximate algorithms for some generalized knapsack problems, An upper bound for the zero-one knapsack problem and a branch and bound algorithm, An algorithm and efficient data structures for the binary knapsack problem, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, A strategy for array management in local memory, Approximation algorithms for the capacitated plant allocation problem, The multidimensional 0-1 knapsack problem: an overview., A note on maximizing a submodular set function subject to a knapsack constraint, Approximation algorithms for knapsack problems with cardinality constraints, Average-case analysis of a greedy algorithm for the 0/1 knapsack problem., Heuristic methods and applications: A categorized survey, A systolic generation of combinations, One-dimensional cutting stock problem to minimize the number of different patterns, Approximation for knapsack problems with multiple constraints, Controlling the losing probability in a monotone game, Machine scheduling with an availability constraint, Elementary team strategies in a monotone game, Worst-case analysis of greedy algorithms for the subset-sum problem, Rational solutions of the graphsack problem, A computer program for constructing a maximum-likelihood map from linkage data and its application to human chromosome 1, Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems, An algorithm for the 0/1 Knapsack problem, Fractional knapsack problems, NP-Complete operations research problems and approximation algorithms
