When greedy gives optimal: a unified approach

DOI10.1016/J.DISOPT.2024.100824MaRDI QIDQ6122087zbMATH OpenOpenAlexWikidataFDO

Authors 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

bin selectioncombinatorial optimizationgreedy algorithmmatroids

Mathematics Subject Classification ID

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

Recommendations

• On the optimality of the greedy solutions of the general knapsack problems
• Sufficient conditions for the optimality of the greedy algorithm in greedoids
• A greedy algorithm for some classes of integer programs.
• On the Greedy Solution of Ordering Problems
• Canonical greedy algorithms and dynamic programming

Cites work

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

Cited in

(1)

• The change-making problem for six coin values and beyond

This page was built for publication: When greedy gives optimal: a unified approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6122087)