Canonical greedy algorithms and dynamic programming

Canonical greedy algorithms and dynamic programming

0.00 Avg rating0 Votes
Article ID: iaor20083399
Country: Poland
Volume: 35
Issue: 3
Start Page Number: 621
End Page Number: 643
Publication Date: Jan 2006
Journal: Control and Cybernetics
Authors:
Keywords: optimization
Abstract:

There has been little work on how to construct greedy algorithms to solve new optimization problems efficiently. Instead, greedy algorithms have generally been designed on an ad hoc basis. On the other hand, dynamic programming has a long history of being a useful tool for solving optimization problems, but is often inefficient. We show how dynamic programming can be used to derive efficient greedy algorithms that are optimal for a wide variety of problems. This approach also provides a way to obtain less efficient but optimal solutions to problems where derived greedy algorithms are nonoptimal.

Reviews

Required fields are marked *. Your email address will not be published.