Auction algorithm

Auction algorithm

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.

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). "A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm", 2006, webpage PDF: [http://www.mit.edu/~devavrat/bpmwm2.pdf MIT-bpmwm-PDF] .] "Handbook of Optimization in Telecommunications", by Mauricio G. C. Resende, Panos M. Pardalos, 2006, 1134 pages, Google Books, webpage: [http://books.google.com/books?id=fp7N4Pk6TG4C&pg=PA204&lpg=PA204&dq=%22auction+algorithm+is%22&source=web&ots=Gqi5gWvrHw&sig=cz6VEVHBI2-mXIwhXjs7CY7rnug GBooks-Handbook-CY7rnug] .]

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. "An Auction Algorithm for Shortest Paths", Dimitri P. Bertsekas, 1991, webpage: [http://citeseer.ist.psu.edu/590528.html PSU-auction-28] .] 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. "The Parallel Auction Algorithm for Weighted Bipartite Matching", E. Jason Riedy, UC Berkeley, February 2004, webpage: [http://www.cs.berkeley.edu/~ejr/tmp/pres-pp04-draft.pdf Berkeley-para4-PDF] .]

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. "A note on the practical performance of the auction algorithm for shortest paths", Jesper Larson, University of Copenhagen, February 1997, webpage: [http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=142 DTU-Views-Auc] .]

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.

ee also

* Hungarian algorithm

Notes

References

* Dimitri P. Bertsekas. "An auction algorithm for shortest paths", "SIAM Journal on Optimization", 1:425 -- 447, 1991, webpage: [http://citeseer.ist.psu.edu/bertsekas91auction.html PSU-bertsekas91auction] .
* "A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm", 2006, webpage PDF: [http://www.mit.edu/~devavrat/bpmwm2.pdf MIT-bpmwm-PDF] .

External links

* Dimitri P. Bertsekas. "An auction algorithm for shortest paths", "SIAM Journal on Optimization", 1:425 -- 447, 1991, webpage: [http://citeseer.ist.psu.edu/bertsekas91auction.html PSU-bertsekas91auction] .


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • auction match algorithm — Auction Matching/ Auction Match Algorithm The process that matches orders at the end of an auction and determines the auction price. London Stock Exchange Glossary …   Financial and business terms

  • auction matching — Auction Matching/ Auction Match Algorithm The process that matches orders at the end of an auction and determines the auction price. London Stock Exchange Glossary …   Financial and business terms

  • Combinatorial auction — A combinatorial auction is a type of smart market in which participants can place bids on combinations of discrete items, or “packages,” rather than just individual items or continuous quantities. Simple combinatorial auctions have been used for… …   Wikipedia

  • Walrasian auction — A Walrasian auction, introduced by Leon Walras, is a type of simultaneous auction where each agent calculates its demand for the good at every possible price and submits this to an auctioneer. The price is then set so that the total demand across …   Wikipedia

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • Resource allocation — is used to assign the available resources in an economic way. It is part of resource management. In project management, resource allocation is the scheduling of activities and the resources required by those activities while taking into… …   Wikipedia

  • Category:Optimization algorithms — An optimization algorithm is an algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x. Here, x can be a scalar or vector of continuous or discrete values …   Wikipedia

  • Assignment problem — The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph. In its most… …   Wikipedia

  • CATS (trading system) — CATS (Computer Assisted Trading System) is an automated exchange system developed for the Toronto Stock Exchange in 1977. CATS was one of the first technologies allowing for a full automation of the price setting process in a stock exchange. This …   Wikipedia

  • Cotation Assistée en Continu — (CAC) was an electronic trading system used at the Paris Bourse, the French stock exchange, in the 1980s and 1990s. It was introduced in 1986 for trading less liquid equities, and in 1989 it was operational for all listed stocks. The acronym is… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”