Computing Partitions with Applications to the Knapsack Problem
From MaRDI portal
Publication:4096145
DOI10.1145/321812.321823zbMath0329.90046OpenAlexW2045492613WikidataQ55878627 ScholiaQ55878627MaRDI QIDQ4096145
Ellis Horowitz, Sartaj K. Sahni
Publication date: 1974
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/5989
Related Items
Generalization of the subset sum problem and cubic forms, Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties, New time-memory trade-offs for subset sum -- improving ISD in theory and practice, A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics, Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection, LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup, Improved Merlin-Arthur protocols for central problems in fine-grained complexity, The Meet-in-the-Middle Principle for Cutting and Packing Problems, INDUCTIVE COMPLEXITY OF THE P VERSUS NP PROBLEM, Subset Sum Quantumly in 1.17 n ., Random knapsack in expected polynomial time, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Unnamed Item, Computational Integrity with a Public Random String from Quasi-Linear PCPs, Solving binary cutting stock problems by column generation and branch- and-bound, Sensitivity Analysis to Perturbations of the Weight of a Subset of Items: The Single Knapsack Case Study, Graph characterization by counting sink star subgraphs, An exact algorithm for the budget-constrained multiple knapsack problem, Inversion of convection-diffusion equation with discrete sources, Assigning channels via the meet-in-the-middle approach, An experimental study of random knapsack problems, On structural decompositions of finite frames, An efficient pruning algorithm for value independent knapsack problem using a DAG structure, A new enumeration scheme for the knapsack problem, Approximation schemes for a class of subset selection problems, An exact decomposition algorithm for the generalized knapsack sharing problem, An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem, Two metaheuristic approaches for solving multidimensional two-way number partitioning problem, GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem, An exact approach for the 0-1 knapsack problem with setups, A low-space algorithm for the subset-sum problem on GPU, Exact approaches for the knapsack problem with setups, On the product knapsack problem, A dynamic programming algorithm for the knapsack problem with setup, An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks, An improved direct descent algorithm for binary knapsack problems, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Approximation schemes for subset-sums ratio problems, The Efficiency of an Algorithm of Integer Programming: A Probabilistic Analysis, Approximating subset sum ratio via subset sum computations, An exact algorithm for large multiple knapsack problems, Change-making problems revisited: a parameterized point of view, Some thoughts on combinatorial optimisation, On an extension of the Sort \& Search method with application to scheduling theory, Complement, Complexity, and Symmetric Representation, Resource allocation for epidemic control across multiple sub-populations, Dynamic programming algorithms for the zero-one knapsack problem, Solution of the zero-one multiple knapsack problem, Integer linear programming model for multidimensional two-way number partitioning problem, A class of nonlinear nonseparable continuous Knapsack and multiple-choice knapsack problems, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach, An algebraic expression of the number partitioning problem, Solving sparse instances of Max SAT via width reduction and greedy restriction, Improved classical and quantum algorithms for subset-sum, Correspondence principle as equivalence of categories, On Bilevel Optimization with Inexact Follower, The complexity of searching in \(X+Y\) and other multisets, New exact algorithms for the 2-constraint satisfaction problem, An improved balanced algorithm for the subset-sum problem, On the connection between Hamming codes, Heapsort and other methods, Branching in branch-and-price: A generic scheme, Two linear approximation algorithms for the subset-sum problem, Qos-aware service evaluation and selection, A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem, Adjacency of the 0-1 knapsack problem, Inductive Complexity of P versus NP Problem, Open problems around exact algorithms, Parallel time and space upper-bounds for the subset-sum problem, Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem, Pattern matching and consensus problems on weighted sequences and profiles, A ``maximum node clustering problem, On exponential time lower bound of Knapsack under backtracking, A quantum particle swarm optimization for the 0-1 generalized knapsack sharing problem, Shift-and-merge technique for the DP solution of the time-constrained backpacker problem, An exact algorithm for the knapsack sharing problem, Faà di Bruno's formula, lattices, and partitions, On the exact separation of mixed integer knapsack cuts, Unnamed Item, Representational information: a new general notion and measure of information, Outbound supply chain network design with mode selection, lead times and capacitated vehicle distribution centers, Faster algorithms for computing power indices in weighted voting games, Sort and Search: exact algorithms for generalized domination, A mixed-integer linear programming model to solve the multidimensional multi-way number partitioning problem, Observations on optimal parallelizations of two-list algorithm, Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Algorithms for the one-dimensional two-stage cutting stock problem, Static main storage packing problems, Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem, An upper bound for the zero-one knapsack problem and a branch and bound algorithm, A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem, Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem, Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study, An algorithm and efficient data structures for the binary knapsack problem, Faster Pseudopolynomial Time Algorithms for Subset Sum, Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights, Solving robust bin-packing problems with a branch-and-price approach, Some New Orders of Hadamard and Skew‐Hadamard Matrices, A complete anytime algorithm for number partitioning, A successive approximation algorithm for the multiple knapsack problem, Cutting optimization with variable-sized stock and inventory status data, Actively secure setup for SPDZ, New trends in exact algorithms for the \(0-1\) knapsack problem, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, A note on the complexity of a partition algorithm, Heuristic and exact algorithms for the precedence-constrained knapsack problem, Moderate exponential-time algorithms for scheduling problems, The zero-one knapsack problem with equality constraint, A new algorithm for optimal 2-constraint satisfaction and its implications, Zero-one integer programs with few contraints - lower bounding theory, Hardness of approximation for knapsack problems, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Specific patterns in the number of lines ofThe Sumerian Temple Hymns, An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual, An exact algorithm for the knapsack sharing problem with common items
