Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Auction_algorithm> ?p ?o }
Showing triples 1 to 36 of
36
with 100 triples per page.
- Auction_algorithm abstract "The term "auction algorithm" applies to several variations of a combinatorial optimization algorithm which solves assignment problems, and network optimization problems with linear and convex/nonlinear cost. 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 original form of the auction algorithm is an iterative method to find the optimal prices and an assignment that maximizes the net benefit in a bipartite graph, the maximum weight matching problem (MWM).This algorithm was first proposed by Dimitri Bertsekas in 1979. Detailed analysis and extensions to more general network optimization problems (ε-relaxation in 1986, and network auction in 1992) are provided in his network optimization books Linear Network Optimization 1991, and Network Optimization: Continuous and Discrete Models 1998. The auction algorithm has excellent computational complexity, as given in these books, and is reputed to be among the fastest for solving single commodity network optimization problems. In addition, the original version of this algorithm is known to possess a distributed nature particularly suitable for distributed systems, since its basic computational primitives (bidding and auctioning) are localized rather than relying on queries of global information. However, the original version that is intrinsically distributable has a pseudo-polynomial time complexity, which means that the running time depends on the input data pattern. Later versions have improved the time complexity to the state-of-the-art level by using techniques such as ε-scaling (also discussed in the original 1979 paper) but at the sacrifice of undermining its distributed characteristics. In order to retain the distributed nature and also attain a polynomial time complexity, recently some researchers from the multi-agent community have been trying to improve the earlier version of the auction algorithm by switching to a different economic model, namely, from the selfish bidders' perspective to a merchant’s point of view, where the merchant of a market adjusts the article prices in order to quickly clear the inventory.The ideas of the auction algorithm and ε-scaling are also central in preflow-push algorithms for single commodity linear network flow problems. In fact the preflow-push algorithm for max-flow can be derived by applying the original 1979 auction algorithm to the max flow problem after reformulation as an assignment problem; see the 1998 Network Optimization book, by Bertsekas, Section 7.3.3. Moreover the preflow-push algorithm for the linear minimum cost flow problem is mathematically equivalent to the ε-relaxation method, which is obtained by applying the original auction algorithm after the problem is reformulated as an equivalent assignment problem.A later variation of the auction algorithm that solves shortest path problems was introduced 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. According to computational experiments, the auction algorithm is generally inferior to other state-of-the-art algorithms for the all destinations shortest path problem, but is very fast for problems with few destinations (substantially more than one and substantially less than the total number of nodes); see the article by Bertsekas, Pallottino, and Scutella, Polynomial Auction Algorithms for Shortest Paths.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.".
- Auction_algorithm wikiPageExternalLink bertsekas91auction.html.
- Auction_algorithm wikiPageExternalLink net.html.
- Auction_algorithm wikiPageExternalLink netbook.html.
- Auction_algorithm wikiPageExternalLink r5717w511x222053.
- Auction_algorithm wikiPageID "15700918".
- Auction_algorithm wikiPageLength "8738".
- Auction_algorithm wikiPageOutDegree "13".
- Auction_algorithm wikiPageRevisionID "662968977".
- Auction_algorithm wikiPageWikiLink Algorithm.
- Auction_algorithm wikiPageWikiLink Assignment_problem.
- Auction_algorithm wikiPageWikiLink Auction.
- Auction_algorithm wikiPageWikiLink Bipartite_graph.
- Auction_algorithm wikiPageWikiLink Category:Optimization_algorithms_and_methods.
- Auction_algorithm wikiPageWikiLink Dimitri_Bertsekas.
- Auction_algorithm wikiPageWikiLink Directed_graph.
- Auction_algorithm wikiPageWikiLink Hungarian_algorithm.
- Auction_algorithm wikiPageWikiLink Matching_(graph_theory).
- Auction_algorithm wikiPageWikiLink Mathematical_optimization.
- Auction_algorithm wikiPageWikiLink Maximum_weight_matching.
- Auction_algorithm wikiPageWikiLink Monotonic_function.
- Auction_algorithm wikiPageWikiLink Optimization_(mathematics).
- Auction_algorithm wikiPageWikiLink Shortest_path_problem.
- Auction_algorithm wikiPageWikiLinkText "Auction algorithm".
- Auction_algorithm wikiPageWikiLinkText "auction algorithm".
- Auction_algorithm hasPhotoCollection Auction_algorithm.
- Auction_algorithm subject Category:Optimization_algorithms_and_methods.
- Auction_algorithm type Algorithm.
- Auction_algorithm comment "The term "auction algorithm" applies to several variations of a combinatorial optimization algorithm which solves assignment problems, and network optimization problems with linear and convex/nonlinear cost. An auction algorithm has been used in a business setting to determine the best prices on a set of products offered to multiple buyers.".
- Auction_algorithm label "Auction algorithm".
- Auction_algorithm sameAs m.03nqgwk.
- Auction_algorithm sameAs Алгоритм_аукціону.
- Auction_algorithm sameAs Q4819604.
- Auction_algorithm sameAs Q4819604.
- Auction_algorithm wasDerivedFrom Auction_algorithm?oldid=662968977.
- Auction_algorithm isPrimaryTopicOf Auction_algorithm.