Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Auction algorithm
open-in-new
<h2 id="comparisons">Comparisons</h2> <p>The (sequential) auction algorithms for the shortest path problem have been the subject of experiments which have been reported in technical papers.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> Experiments clearly show that the auction algorithm is inferior to the state-of-the-art shortest-path algorithms for finding the optimal solution of single-origin to all-destinations problems.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> </p><p>Although with the auction algorithm the total benefit is <a href="/facts/Monotonic_function/MjQK0YL2">monotonically increasing</a> with each iteration, in the <i><a href="/facts/Hungarian_algorithm/rRCJebc1">Hungarian algorithm</a></i> (from Kuhn, 1955; Munkres, 1957) the total benefit strictly increases with each iteration. </p><p>The auction algorithm of Bertsekas for finding shortest paths within a directed graph is reputed to perform very well on random graphs and on problems with few destinations.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Hungarian_algorithm/rRCJebc1">Hungarian algorithm</a></li></ul> <h2 id="external-links">External links</h2> <ul><li>Dimitri P. Bertsekas. "Linear Network Optimization", MIT Press, 1991, <a href="http://web.mit.edu/dimitrib/www/net.html">on-line</a>.</li> <li>Dimitri P. Bertsekas. "Network Optimization: Continuous and Discrete Models", <a href="http://www.athenasc.com/netbook.html">Athena Scientific, 1998</a>.</li> <li>Dimitri P. Bertsekas. "An auction algorithm for shortest paths", <i>SIAM Journal on Optimization</i>, 1:425—447, 1991, webpage: <a href="http://citeseer.ist.psu.edu/bertsekas91auction.html">PSU-bertsekas91auction</a>.</li> <li>D.P. Bertsekas, S. Pallottino, M. G. Scutella. "Polynomial Auction Algorithms for Shortest Paths," <a href="https://doi.org/10.1007%2FBF01302891">Computational Optimization and Applications</a>, Vol. 4, 1995, pp. 99-125.</li> <li>Implementation of Bertsekas' Auction algorithm in Matlab by Florian Bernard, webpage: <a href="http://de.mathworks.com/matlabcentral/fileexchange/48448-fast-linear-assignment-problem-using-auction-algorithm--mex-">Matlab File Exchange</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Dimitri P. Bertsekas. "A distributed algorithm for the assignment problem", original paper, 1979. <a href="/wiki/Dimitri_P._Bertsekas" target="_blank">/wiki/Dimitri_P._Bertsekas</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>M.G. Resende, P.M. Pardalos. "Handbook of optimization in telecommunications", 2006 <a href="/wiki/Mauricio_Resende" target="_blank">/wiki/Mauricio_Resende</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>M. Bayati, D. Shah, M. Sharma. "A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm", 2006, webpage PDF: MIT-bpmwm-PDF Archived 2017-09-21 at the Wayback Machine. <a href="https://www.mit.edu/~devavrat/bpmwm2.pdf" target="_blank">https://www.mit.edu/~devavrat/bpmwm2.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Dimitri P. Bertsekas. "A distributed algorithm for the assignment problem", original paper, 1979. <a href="/wiki/Dimitri_P._Bertsekas" target="_blank">/wiki/Dimitri_P._Bertsekas</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Bertsekas, Dimitri (December 1986). "Distributed relaxation methods for linear network flow problems". 1986 25th IEEE Conference on Decision and Control. IEEE. pp. 2101–2106. doi:10.1109/cdc.1986.267433. <a href="/wiki/Dimitri_Bertsekas" target="_blank">/wiki/Dimitri_Bertsekas</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Dimitri P. Bertsekas. "An auction algorithm for shortest paths", SIAM Journal on Optimization, 1:425—447, 1991,PSU-bertsekas91auction <a href="http://citeseer.ist.psu.edu/bertsekas91auction.html" target="_blank">http://citeseer.ist.psu.edu/bertsekas91auction.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Dimitri P. Bertsekas. "An auction algorithm for shortest paths", SIAM Journal on Optimization, 1:425—447, 1991,PSU-bertsekas91auction <a href="http://citeseer.ist.psu.edu/bertsekas91auction.html" target="_blank">http://citeseer.ist.psu.edu/bertsekas91auction.html</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Dimitri P. Bertsekas. "An auction algorithm for shortest paths", SIAM Journal on Optimization, 1:425—447, 1991,PSU-bertsekas91auction <a href="http://citeseer.ist.psu.edu/bertsekas91auction.html" target="_blank">http://citeseer.ist.psu.edu/bertsekas91auction.html</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>"The Parallel Auction Algorithm for Weighted Bipartite Matching", E. Jason Riedy, UC Berkeley, February 2004, [1]. <a href="http://jriedy.users.sonic.net/resume/material/pp04.pdf" target="_blank">http://jriedy.users.sonic.net/resume/material/pp04.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Larsen, Jesper; Pedersen, Ib (1999). "Experiments with the auction algorithm for the shortest path problem". Nordic Journal of Computing. 6 (4): 403–42. ISSN 1236-6064., see also A note on the practical performance of the auction algorithm for the shortest path Archived 2011-06-05 at the Wayback Machine (1997) by the first author. <a href="http://portal.acm.org/citation.cfm?id=642163" target="_blank">http://portal.acm.org/citation.cfm?id=642163</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Larsen, Jesper; Pedersen, Ib (1999). "Experiments with the auction algorithm for the shortest path problem". Nordic Journal of Computing. 6 (4): 403–42. ISSN 1236-6064., see also A note on the practical performance of the auction algorithm for the shortest path Archived 2011-06-05 at the Wayback Machine (1997) by the first author. <a href="http://portal.acm.org/citation.cfm?id=642163" target="_blank">http://portal.acm.org/citation.cfm?id=642163</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Dimitri P. Bertsekas. "An auction algorithm for shortest paths", SIAM Journal on Optimization, 1:425—447, 1991,PSU-bertsekas91auction <a href="http://citeseer.ist.psu.edu/bertsekas91auction.html" target="_blank">http://citeseer.ist.psu.edu/bertsekas91auction.html</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> </ol>