Fast Approximation Algorithms for Knapsack Problems
From MaRDI portal
Publication:3861164
DOI10.1287/moor.4.4.339zbMath0425.90064OpenAlexW2113195911WikidataQ94701723 ScholiaQ94701723MaRDI QIDQ3861164
Publication date: 1979
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.4.4.339
NP-complete problemsknapsack problemapproximate solutionsubset sum problemfully polynomial approximation schemes
Related Items
Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints, Multistage knapsack, An asymptotically exact polynomial algorithm for equipartition problems, An exact algorithm for the 0-1 collapsing knapsack problem, An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, A compact labelling scheme for series-parallel graphs, The 2-quasi-greedy algorithm for cardinality constrained matroid bases, An FPTAS for the parametric knapsack problem, Approximation algorithms for the capacitated plant allocation problem, Rectangle packing with one-dimensional resource augmentation, An approximate binary search algorithm for the multiple-choice knapsack problem, One-machine generalized precedence constrained scheduling problems, Approximation algorithms for hard capacitated \(k\)-facility location problems, A new enumeration scheme for the knapsack problem, APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS, The linking set problem: a polynomial special case of the multiple-choice knapsack problem, An efficient approximation for the generalized assignment problem, Approximation schemes for a class of subset selection problems, Resource allocation problem under single resource assignment, Integer knapsack problems with set-up weights, Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints, A nonlinear knapsack problem, An exact algorithm for the modular hub location problem with single assignments, Improved algorithms for two single machine scheduling problems, Stochastic budget optimization in internet advertising, An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks, Approximation and online algorithms for multidimensional bin packing: a survey, Stochastic Knapsack Revisited: The Service Level Perspective, An improved heuristic for one-machine scheduling with delays constraints, On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks, A new fully polynomial time approximation scheme for the interval subset sum problem, An approximation algorithm for solving unconstrained two-dimensional knapsack problems, Reoptimizing the 0-1 knapsack problem, A faster FPTAS for the unbounded knapsack problem, Computing knapsack solutions with cardinality robustness, On the machine scheduling problem with job delivery coordination, Unnamed Item, A Fast Approximation Algorithm For The Subset-Sum Problem, On inequalities with bounded coefficients and pitch for the min knapsack polytope, An improved binary search algorithm for the Multiple-Choice Knapsack Problem, A Polynomial Time Approximation Scheme for the Square Packing Problem, Approximation algorithms and relaxations for a service provision problem on a telecommunication network, An efficient fully polynomial approximation scheme for the Subset-Sum problem., Minimum and worst-case performance ratios of rollout algorithms, A note on maximizing the spread of influence in social networks, Exact algorithms for the guillotine strip cutting/packing problem., Unnamed Item, Improved Algorithm for Resource Allocation Problems, An algorithm for the solution of the 0-1 knapsack problem, The Unbounded Knapsack Problem, Near optimal multiple choice index selection for relational databases, Probabilistic analysis of the subset-sum problem, The multidimensional 0-1 knapsack problem: an overview., Some extended knapsack problems involving job partition between two parties, Algorithms for the bounded set-up knapsack problem, An improved approximation scheme for variable-sized bin packing, Nonconvex piecewise linear knapsack problems, Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets, Complexity and algorithms for nonlinear optimization problems, A fast asymptotic approximation scheme for bin packing with rejection, Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem, Strip generation algorithms for constrained two-dimensional two-staged cutting problems, Worst-case analysis of greedy algorithms for the subset-sum problem, Minimum-diameter covering problems, Unnamed Item, The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem, Unnamed Item, An exact algorithm for the subset sum problem, On the approximability of the two-phase knapsack problem, A pegging algorithm for the nonlinear resource allocation problem, Approximation algorithms for scheduling with reservations, Convex Relaxations and Integrality Gaps, On fair price discrimination in multi-unit markets, Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times, Faster Pseudopolynomial Time Algorithms for Subset Sum, A Survey on Approximation Algorithms for Scheduling with Machine Unavailability, Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem, Approximate algorithms for the Knapsack problem on parallel computers, A successive approximation algorithm for the multiple knapsack problem, A new heuristic algorithm for the machine scheduling problem with job delivery coordination, A new linear storage, polynomial-time approximation scheme for the subset-sum problem, Heuristic methods and applications: A categorized survey, Approximation algorithms for knapsack problems with cardinality constraints, On social envy-freeness in multi-unit markets, Estimating the probability of meeting a deadline in schedules and plans, Unnamed Item, Scheduling jobs with time-resource tradeoff via nonlinear programming, Approximations to clustering and subgraph problems on trees, The matroidal knapsack: A class of (often) well-solvable problems, The nonlinear knapsack problem - algorithms and applications, Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems, Optimizing a mail-order with discount and shipping costs, Approximation schemes for the subset-sum problem: Survey and experimental analysis, A Time–Cost Tradeoff Problem with Multiple Assessments and Release Times on a Chain Precedence Graph, The quadratic 0-1 knapsack problem with series-parallel support, Approximation algorithms for fractional knapsack problems, Approximation schemes for multiperiod binary knapsack problems, An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem, General bounds for incremental maximization, New approximability results for two-dimensional bin packing, The multidimensional 0-1 knapsack problem -- bounds and computational aspects
