Approximate Algorithms for the 0/1 Knapsack Problem
From MaRDI portal
Publication:4136930
DOI10.1145/321864.321873zbMath0362.90066OpenAlexW2089047615WikidataQ97016584 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
Numerical mathematical programming methods (65K05) Integer programming (90C10) Algorithms in computer science (68W99)
Related Items
An asymptotically exact polynomial algorithm for equipartition problems, On different approximation criteria for subset product problems, A strategy for array management in local memory, Generic properties of a computational task predict human effort and performance, Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems, Approximation algorithms for the capacitated plant allocation problem, Packing Under Convex Quadratic Constraints, Parallel generation of permutations and combinations, Shrinking maxima, decreasing costs: new online packing and covering problems, A new enumeration scheme for the knapsack problem, Solving 0 - 1 knapsack problem by artificial chemical reaction optimization algorithm with a greedy strategy, APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS, Gaussian downlink user selection subject to access limit, power budget, and rate demands, The knapsack problem with generalized upper bounds, Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work, Reoptimizing the 0-1 knapsack problem, Unnamed Item, Prioritizing municipal lead mitigation projects as a relaxed knapsack optimization: a method and case study, Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties, On approximating the incremental knapsack problem, Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints, How to optimize storage classes in a unit-load warehouse, Approximation schemes for generalized two-dimensional vector packing with application to data placement, Minimum and worst-case performance ratios of rollout algorithms, Vector bin packing with multiple-choice, Discrete extremal problems, A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem, Approximation for knapsack problems with multiple constraints, The multidimensional 0-1 knapsack problem: an overview., A note on maximizing a submodular set function subject to a knapsack constraint, Single-vendor multi-buyer inventory coordination under private information, Optimal and efficient adaptation in distributed real-time systems with discrete rates, Distributed approximation of \(k\)-service assignment, Approximation algorithms on 0--1 linear knapsack problem with a single continuous variable, A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles, Bandwidth allocation in cellular networks with multiple interferences, Online budgeted maximum coverage, Approximate solution of NP optimization problems, Approximation schemes for the parametric knapsack problem, Nonconvex piecewise linear knapsack problems, Rational solutions of the graphsack problem, A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem, FPTAS for the two identical parallel machine problem with a single operator under the free changing mode, A computer program for constructing a maximum-likelihood map from linkage data and its application to human chromosome 1, Controlling the losing probability in a monotone game, Playing monotone games to understand learning behaviors, Principles and applications of continual computation, Worst-case analysis of greedy algorithms for the subset-sum problem, An algorithm for the 0/1 Knapsack problem, Approximate algorithms for some generalized knapsack problems, Fractional 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, Packing resizable items with application to video delivery over wireless networks, Average-case analysis of a greedy algorithm for the 0/1 knapsack problem., The zone hopping problem, NP-Complete operations research problems and approximation algorithms, Heuristic methods and applications: A categorized survey, A systolic generation of combinations, Approximation algorithms for knapsack problems with cardinality constraints, Machine scheduling with an availability constraint, Market-based pricing in grids: on strategic manipulation and computational cost, Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Elementary team strategies in a monotone game, Data dependent worst case bound improving techniques in zero-one programming, Improved approximation algorithms for a bilevel knapsack problem, One-dimensional cutting stock problem to minimize the number of different patterns, Packing under convex quadratic constraints, The multidimensional 0-1 knapsack problem -- bounds and computational aspects
