| Автор | Cerulli, R. |
| Автор | De Leone, R. |
| Автор | Piacente, G. |
| Дата выпуска | 1994 |
| dc.description | A modified auction algorithm for solving the shortest path problem is presented and convergence is established. The proposed method differs from the standard auction algorithm in the way dual variables are updated. By relaxing the dual feasibility requirement we were able to reduce the total number of iterations required by the auction algorithm to compute the shortest path. Computational results show the advantage of this new approach, especially when the number of intermediate nodes in the shortest path from the origin to the destination is large. |
| Формат | application.pdf |
| Издатель | Gordon and Breach Science Publishers |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Тема | Auction algorithm, shortest path |
| Название | A modified auction algorithm for the shortest path problem |
| Тип | research-article |
| DOI | 10.1080/10556789408805588 |
| Electronic ISSN | 1029-4937 |
| Print ISSN | 1055-6788 |
| Журнал | Optimization Methods and Software |
| Том | 4 |
| Первая страница | 209 |
| Последняя страница | 224 |
| Аффилиация | Cerulli, R.; Dipartimento di Informatica e Applicazioni, Università di Salerno |
| Аффилиация | De Leone, R.; Center for Parallel Optimization, Computer Sciences Department, University of Wisconsin Madison |
| Аффилиация | Piacente, G.; Dipartimento di Matematica, Università di Camerino |
| Выпуск | 3 |
| Библиографическая ссылка | Bertsekas, D.P. 1979. “A distributed algorithm for the assignment problem. Technical report, Laboratory for Information and Decision System”. Cambridge: Massachusetts Institute of Technology. |
| Библиографическая ссылка | Bertsekas, D.R. A distributed asynchronous relaxation algorithm for the assignment problem. 24th IEEE Conference on Decwon and Control. Ft Lauderdale, Fla. pp.1703–1704. |
| Библиографическая ссылка | Bertsekas, D.R. 1988. The auction algorithm: A distributed relaxation method for the assignment problems. Annals of Operation Research, 14: 105–123. |
| Библиографическая ссылка | Bertsekas, D.R. and Castanon, D.A. 1989. “The auction algorithm for the minimum cost network flow problem”. Cambridge: Massachusetts Institute of Technology. Technical Report LIDS-P-1925, Laboratory for Information and Decision System |
| Библиографическая ссылка | Bertsekas, D.R. and Castanon, D.A. 1989. The auction algorithm for transportation problems. Annals of Operation Research, 20: 67–96. |
| Библиографическая ссылка | Bertsekas, D.R. and Castanon, D.A. 1991. “A generic auction algorithm for the minimum cost network flow problem”. Cambridge: Massachusetts Institute of Technology. Technical Report LIDS-P-2084, Laboratory for Information and Decision System |
| Библиографическая ссылка | Bertsekas, D.R. 1991. Linear Network Optimization-Algorithms and Codes, Cambridge, Massachusetts: The MIT Press. |
| Библиографическая ссылка | Bertsekas, D.R. 1991. An auction algorithm for shortest paths. SIAM Journal on Optimization, 1(4): 425–447. |
| Библиографическая ссылка | Pallottino, S. and Scutellà, M.G. 1991. Strongly polynomial auction algorithms for shortest paths. Ricerca Operativa, 21(60): 33–53. |
| Библиографическая ссылка | Bertsekas, D.R. November 1992. “Another modified auction/shortest path algorithm”. November, Manuscript. |
| Библиографическая ссылка | Nemhauser, G.L. and Wolsey, L.A. 1988. Integer and Combinatorial Optimization, John Wiley & Sons. |
