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 (only showing first 100 items - show all)
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
This page was built for publication: Computing Partitions with Applications to the Knapsack Problem
