Термін алгори́тм аукціо́нуBayati, M.; Shah, D.; Sharma, M. (2006). A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm. pp. 557. () використовується для позначення кількох варіантів алгоритмів комбінованої оптимізації при вирішенні задач призначення і задач мережної оптимізації з лінійними чи нелінійними витратами. Алгоритм аукціону використовується у бізнес рішеннях для визначення найкращих цін на набір продуктів, запропонованих для кількох покупців. Він використовує ітераційний метод, оскільки назва «алгоритм аукціону» відсилає до поняття торгового аукціону, де паралельні ставки порівнюються для визначення найкращої пропозиції, а остаточний продаж відбувається за найвищої ставки.
Початковою формою алгоритму аукціону був метод ітерацій для пошуку оптимальної ціни і призначення, які максимізували б чисті вигоди у двочастковому графіку, у задачах парування (теорії графів)Resende, Mauricio G. C.; Pardalos, Panos M. (2006), Handbook of optimization in telecommunications, Birkhäuser, ISBN 978-0-387-30662-9, retrieved 10 March 2010. Цей алгоритм вперше запропонував Дімітрій Берцекас у 1979 р. Докладний аналіз і розширення для більш загальних задач мережною оптимізації (іпсилон-послаблення і алгоритми мережних аукціонів) наведений у його книжках з мережної оптимізації «Оптимізація лінійних мереж» (1991) та «Мережна оптимізація: Неперервні та Дискретні моделі» (1998). Алгоритм аукціону має найвищу обчислювальну складність, згідно з цими книжками, і вважається одним з найшвидших методів вирішення простих споживацьких задач мережної оптимізації.
Пізніший варіант алгоритму аукціону, котрий розв'язує задачу про найкоротший шлях, був запропонований Берцекасом у 1991 р.Bertsekas, D. P. (1991). «An Auction Algorithm for Shortest Paths». SIAM Journal on Optimization 1 (4): 425 Це простий алгоритм для знаходження найкоротшого шляху в орієнтованому графі. У випадку однієї початкової та однією точки призначення, алгоритм аукціону будує один шлях від початкової точки, який розширюється пізніше чи обумовлюється окремим вузлом при кожній ітерації. При цьому щонайбільше одна подвійна змінна буде відкоригована при одній ітерації для того, щоб вдосконалити або зберегти значення подвійної функції. Алгоритм аукціону добре підходить для паралельного обрахунку у випадку кількох початкових точок. Також цей алгоритм тісно пов'язаний з алгоритмами аукціону для інших задач мережних потоків. Згідно з експериментальними обчисленнями, алгоритм аукціону є нижчим порівняно до інших впроваджених алгоритмів для усіх проблем найкоротшого шляху, але є дуже швидким для проблем з невеликою кількістю точок призначень (переважно більше однієї та менше за загальну кількість вузлів), див. статтю Берцекас, Паллотіно і Скутелла, Polynomial Auction Algorithms for Shortest Paths.
Алгоритми аукціону для найкоротшого гіпершляху були визначені Де Леоне та Претолані у 1998 р. це також алгоритм паралельного аукціону для зваженого двочасткового зіставлення, описаного Е. Джейсоном Ріді у 2004.«The Parallel Auction Algorithm for Weighted Bipartite Matching», E. Jason Riedy, UC Berkeley, February 2004
Порівняння
(Послідовний) алгоритм аукціону для задач найкоротшого шляху став предметом експериментів, описаних в спеціалізованих технічних виданняхLarsen, Jesper; Pedersen, Ib (1999). «Experiments with the auction algorithm for the shortest path problem». Nordic J. of Computing 6 (4): 403-42, див. також Larsen, Jesper «A note on the practical performance of the auction algorithm for the shortest path» (1997). Ці експерименти чітко продемонстрували, що алгоритми аукціону є нижчими до впроваджених алгоритмів найкоротшого шляху для знаходження оптимального рішення.
Хоча в алгоритмі аукціону жодна ітерація ніколи не зменшує загальних вигід (або збільшує, або залишає на тому ж рівні), в альтернативному Угорському алгоритмі (за Куном, 1955, Мункрес, 1957) кожна ітерація покращує результат.
Вважається, що алгоритм аукціону Бертцекаса для знаходження найкоротшого шляху на орієнтованому графі дуже добре справляється у випадку випадкових кривих і у випадку задач з кількома точками призначення.
Див. також
Алгоритм Задача оптимізації
Примітки
Джерела Дімітрі Бертцекас, Стефано Паллотіно та Марія Грація Скутелла Polynomial auction algorithms for shortest paths