| rdfs: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. 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. (en)
- Термін алгори́тм аукціо́ну (англ. Auction algorithm) використовується для позначення кількох варіантів алгоритмів комбінованої оптимізації при вирішенні задач призначення і задач мережної оптимізації з лінійними чи нелінійними витратами. Алгоритм аукціону використовується у бізнес рішеннях для визначення найкращих цін на набір продуктів, запропонованих для кількох покупців. Він використовує ітераційний метод, оскільки назва «алгоритм аукціону» відсилає до поняття торгового аукціону, де паралельні ставки порівнюються для визначення найкращої пропозиції, а остаточний продаж відбувається за найвищої ставки. (uk)
|
| has 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. 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. 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. (en)
- Термін алгори́тм аукціо́ну (англ. Auction algorithm) використовується для позначення кількох варіантів алгоритмів комбінованої оптимізації при вирішенні задач призначення і задач мережної оптимізації з лінійними чи нелінійними витратами. Алгоритм аукціону використовується у бізнес рішеннях для визначення найкращих цін на набір продуктів, запропонованих для кількох покупців. Він використовує ітераційний метод, оскільки назва «алгоритм аукціону» відсилає до поняття торгового аукціону, де паралельні ставки порівнюються для визначення найкращої пропозиції, а остаточний продаж відбувається за найвищої ставки. Початковою формою алгоритму аукціону був метод ітерацій для пошуку оптимальної ціни і призначення, які максимізували б чисті вигоди у двочастковому графіку, у задачах парування (теорії графів). Цей алгоритм вперше запропонував Дімітрій Берцекас у 1979 р. Докладний аналіз і розширення для більш загальних задач мережною оптимізації (іпсилон-послаблення і алгоритми мережних аукціонів) наведений у його книжках з мережної оптимізації «Оптимізація лінійних мереж» (1991) та «Мережна оптимізація: Неперервні та Дискретні моделі» (1998). Алгоритм аукціону має найвищу обчислювальну складність, згідно з цими книжками, і вважається одним з найшвидших методів вирішення простих споживацьких задач мережної оптимізації. Пізніший варіант алгоритму аукціону, котрий розв'язує задачу про найкоротший шлях, був запропонований Берцекасом у 1991 р. Це простий алгоритм для знаходження найкоротшого шляху в орієнтованому графі. У випадку однієї початкової та однією точки призначення, алгоритм аукціону будує один шлях від початкової точки, який розширюється пізніше чи обумовлюється окремим вузлом при кожній ітерації. При цьому щонайбільше одна подвійна змінна буде відкоригована при одній ітерації для того, щоб вдосконалити або зберегти значення подвійної функції. Алгоритм аукціону добре підходить для паралельного обрахунку у випадку кількох початкових точок. Також цей алгоритм тісно пов'язаний з алгоритмами аукціону для інших задач мережних потоків. Згідно з експериментальними обчисленнями, алгоритм аукціону є нижчим порівняно до інших впроваджених алгоритмів для усіх проблем найкоротшого шляху, але є дуже швидким для проблем з невеликою кількістю точок призначень (переважно більше однієї та менше за загальну кількість вузлів), див. статтю Берцекас, Паллотіно і Скутелла, Polynomial Auction Algorithms for Shortest Paths[недоступне посилання з грудня 2019]. Алгоритми аукціону для найкоротшого гіпершляху були визначені Де Леоне та Претолані у 1998 р. це також алгоритм паралельного аукціону для зваженого двочасткового зіставлення, описаного Е. Джейсоном Ріді у 2004. (uk)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)