Auction Algorithms for Network Flow Problems: A Tutorial Introduction Export

@article{citeulike:761275, abstract = {An extensive tutorial paper that surveys auction algorithms, a comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a real auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.}, author = {Bertsekas, Dimitri}, citeulike-article-id = {761275}, journal = {Computational Optimization and Applications}, keywords = {auctions, distributed-computing}, pages = {7--66}, posted-at = {2006-07-16 16:16:15}, priority = {2}, title = {Auction Algorithms for Network Flow Problems: A Tutorial Introduction}, volume = {1}, year = {1992} }

TY - JOUR ID - citeulike:761275 L3 - citeulike-article-id:761275 N2 - An extensive tutorial paper that surveys auction algorithms, a comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a real auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation. JF - Computational Optimization and Applications EP - 66 TI - Auction Algorithms for Network Flow Problems: A Tutorial Introduction VL - 1 SP - 7 KW - auctions KW - distributed-computing AU - Bertsekas, Dimitri PY - 1992/// ER -