Approximate Algorithms for the 0/1 Knapsack Problem

Cited In (70)

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

This page was built for publication: Approximate Algorithms for the 0/1 Knapsack Problem

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