When the Greedy Solution Solves a Class of Knapsack Problems
From MaRDI portal
Publication:4062195
DOI10.1287/opre.23.2.207zbMath0305.90039OpenAlexW2034751042MaRDI QIDQ4062195
Nemhauser, George I., Leslie E. jun. Trotter, Michael J. Magazine
Publication date: 1975
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.23.2.207
Related Items (32)
What's in \textit{YOUR} wallet? ⋮ Unnamed Item ⋮ Fractal patterns related to dividing coins ⋮ A new lower bound for the linear knapsack problem with general integer variables ⋮ On variations of the subset sum problem ⋮ Motion planning with pulley, rope, and baskets ⋮ Change-making problems revisited: a parameterized point of view ⋮ Dynamic programming algorithms for the zero-one knapsack problem ⋮ Optimal and canonical solutions of the change making problem ⋮ On the greedy solution in integer linear programming ⋮ When greedy gives optimal: a unified approach ⋮ The correction term for the Riemann-Roch formula of cyclic quotient singularities and associated invariants ⋮ On the optimality of the greedy solutions of the general knapsack problems ⋮ On \(n\)-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets ⋮ A heuristic algorithm for a chance constrained stochastic program ⋮ Convex hulls of superincreasing knapsacks and lexicographic orderings ⋮ Characterization of canonical systems with six types of coins for the change-making problem ⋮ An exact algorithm for large unbounded knapsack problems ⋮ An extension of a greedy heuristic for the knapsack problem ⋮ The capacitated budgeted minimum cost flow problem with unit upgrading costs ⋮ A total-value greedy heuristic for the integer knapsack problem ⋮ A constructive periodicity bound for the unbounded knapsack problem ⋮ A solution method for a knapsack problem and its variant ⋮ Unbounded knapsack problems with arithmetic weight sequences ⋮ A polynomially solvable special case of the unbounded knapsack problem ⋮ Fractional knapsack problems ⋮ A hybrid approach to discrete mathematical programming ⋮ Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation ⋮ The zone hopping problem ⋮ Heuristic methods and applications: A categorized survey ⋮ Combinatorics of the change-making problem ⋮ An application of an optimal behaviour of the greedy solution in number theory
This page was built for publication: When the Greedy Solution Solves a Class of Knapsack Problems
