Canonical greedy algorithms and dynamic programming

• Autorzy: Lew A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

greedy algorithm; dynamic programming; Dijkstra

PL

programowanie dynamiczne; algorytm Dijkstry

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 3
• Strony: 621--643
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Lew A.

• Department of Information and Computer Sciences, University of Hawaii at Manoa, USA,

Bibliografia

• BELLMAN, R. (1957) Dynamic Programming. Princeton University Press, Princeton.
• BIRD, R. and DE MOOR, O. (1993) From dynamic programming to greedy algorithms. Formal Program Development, LNCS 755, 43-61.
• BORODIN, A., NIELSEN, M.N. and RACKOFF, C. (2002) (Incremental) priority algorithms. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 752-761.
• GORMEN, T.H., LEISERSON. C.E., RIVEST, R.L. and STEIN, C. (2001) Introduction to Algorithms, 2nd Ed. McGraw-Hill, New York.
• CURTIS, S. (2003) The classification of greedy algorithms. Science of Computer Programming 49, 125-157.
• DAVIS S. and IMPAGLIAZZO, R. (2004) Models of greedy algorithms for graph problems. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 381-390.
• DREYFUSS S.E. and LAW, A.M. (1977) The Art and Theory of Dynamic Programming. Academic Press, New York.
• HELMAN, P., MORET, B.M.E. and SHAPIRO, H. (1993) An exact characterization of greedy structures. SIAM J. on Discrete Mathematics 6, 274-283.
• HEYMAN, S.P. and SOBEL, M.J. (1984) Stochastic Models in Operations Research, Volume II. Academic Press, New York.
• HILLIER F.S. and LIEBERMAN, G.J. (2001) Introduction to Operations Research, 7th Ed. McGraw-Hill, New York.
• HOROWITZ, E., SAHNI. S. and RAJASEKARAN, S. (1996) Computer Algorithms/ C++. Computer Science Press, New York.
• LEW, A. (1985) Computer Science: A Mathematical Introduction. Prentice-Hall International. London.
• PAPADIMITRIOU, C.H. and STEIGLITZ, K. (1982) Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs.
• SNIEDOVICH, M. (2006) Dijkstra's algorithm revisited: the dynamic programming connexion. J. Control and Cybernetics, (this issue).
• WINSTON, W.L. (2004) Operations Research: Applications and Algorithms, 4th Ed. Brooks/Cole, Belmont.