When greedy gives optimal: a unified approach

DOI10.1016/j.disopt.2024.100824OpenAlexW4391218068WikidataQ129334947 ScholiaQ129334947MaRDI QIDQ6122087

Dmitry Rybin

Publication date: 27 March 2024

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2024.100824

zbMATH Keywords

combinatorial optimizationgreedy algorithmmatroidsbin selection

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• A polynomial-time algorithm for knapsack with divisible item sizes
• Convex hulls of superincreasing knapsacks and lexicographic orderings
• A polynomial algorithm for the multiple knapsack problem with divisible item sizes
• Combinatorics of the change-making problem
• An application of an optimal behaviour of the greedy solution in number theory
• Change-making problems revisited: a parameterized point of view
• A polynomial-time algorithm for the change-making problem
• When the Greedy Solution Solves a Class of Knapsack Problems
• Canonical Coin Changing and Greedy Solutions
• Technical Note—Optimality of a Heuristic Solution for a Class of Knapsack Problems
• Error Bounds and the Applicability of the Greedy Solution to the Coin-Changing Problem
• A polynomially solvable special case of the unbounded knapsack problem