Added to Favorites

Related Searches

Nearby Words

The term "auction algorithm" applies to several variations of a combinatorial optimization algorithm which solves assignment problems, including forward/reverse auction algorithms. An auction algorithm has been used in a business setting to determine the best prices on a set of products offered to multiple buyers. It is an iterative procedure, so the name "auction algorithm" is related to a sales auction, where multiple bids are compared to determine the best offer, with the final sales going to the highest bidders.## Comparisons

The (sequential) auction algorithms for the shortest path problem have been the subject of experiments which have been reported in technical papers. Experiments clearly show that the auction algorithm is inferior to the state-of-the-art shortest-path algorithms for finding the optimal solution.## See also

## Notes

## References

## External links

The auction algorithm is an iterative method to find the optimal prices and an assignment that maximizes the net benefit, and is therefore the maximum weight matching (MWM).

An early auction algorithm was defined by Dimitri P. Bertsekas in 1988, with a later variation as an auction algorithm for shortest paths by Bertsekas in 1991. It is a simple algorithm for finding shortest paths in a directed graph. In the single origin/single destination case, the auction algorithm maintains a single path starting at the origin, which is then extended or contracted by a single node at each iteration. Simultaneously, at most one dual variable will be adjusted at each iteration, in order to either improve or maintain the value of a dual function. In the case of multiple origins, the auction algorithm is well-suited for parallel computation. The algorithm is closely related to auction algorithms for other network flow problems.

Auction algorithms for shortest hyperpath problems have been defined by De Leone and Pretolani in 1998. This is also a parallel auction algorithm for weighted bipartite matching, described by E. Jason Riedy in 2004.

Although in the auction algorithm, each iteration never decreases the total benefit (increases or remains the same), with the alternative Hungarian algorithm (from Kuhn, 1955; Munkres, 1957), each iteration always increases the total.

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.

- Dimitri P. Bertsekas. "An auction algorithm for shortest paths", SIAM Journal on Optimization, 1:425 -- 447, 1991, webpage: PSU-bertsekas91auction
- "A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm", 2006, webpage PDF: MIT-bpmwm-PDF

- Dimitri P. Bertsekas. "An auction algorithm for shortest paths", SIAM Journal on Optimization, 1:425 -- 447, 1991, webpage: PSU-bertsekas91auction

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 08, 2008 at 02:50:35 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 08, 2008 at 02:50:35 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.