Fast Approximation Algorithms for Knapsack Problems
From MaRDI portal
Publication:3861164
DOI10.1287/MOOR.4.4.339zbMath0425.90064DBLPjournals/mor/Lawler79OpenAlexW2113195911WikidataQ94701723 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 (only showing first 100 items - show all)
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
This page was built for publication: Fast Approximation Algorithms for Knapsack Problems
