Термин « алгоритм аукциона » [1] применяется к нескольким вариациям алгоритма комбинаторной оптимизации , который решает задачи назначения и задачи сетевой оптимизации с линейной и выпуклой/нелинейной стоимостью. Алгоритм аукциона использовался в бизнес-среде для определения лучших цен на набор продуктов, предлагаемых нескольким покупателям. Это итеративная процедура, поэтому название «алгоритм аукциона» связано с аукционом продаж , где сравниваются несколько ставок для определения наилучшего предложения, а окончательные продажи достаются тем, кто сделал самую высокую ставку.
Первоначальная форма алгоритма аукциона представляет собой итеративный метод поиска оптимальных цен и назначения, которое максимизирует чистую выгоду в двудольном графе , задача максимального соответствия весов (MWM). [2] [3] Этот алгоритм был впервые предложен Дмитрием Берцекасом в 1979 году.
Идеи алгоритма аукциона и ε-масштабирования [1] также являются центральными в алгоритмах preflow-push для задач линейного сетевого потока с одним товаром. Фактически алгоритм preflow-push для максимального потока может быть получен путем применения оригинального алгоритма аукциона 1979 года к задаче максимального потока после переформулирования в задачу назначения. Более того, алгоритм preflow-push для линейной задачи потока минимальной стоимости математически эквивалентен методу ε-релаксации, который получается путем применения оригинального алгоритма аукциона после переформулирования задачи в эквивалентную задачу назначения. [4]
Более поздняя вариация алгоритма аукциона, решающая задачи поиска кратчайшего пути, была представлена Берцекасом в 1991 году. [5] Это простой алгоритм для поиска кратчайших путей в ориентированном графе . В случае одного источника/одного пункта назначения алгоритм аукциона поддерживает один путь, начинающийся в источнике, который затем расширяется или сужается одним узлом на каждой итерации. Одновременно на каждой итерации будет корректироваться не более одной двойственной переменной, чтобы либо улучшить, либо сохранить значение двойственной функции. В случае нескольких источников алгоритм аукциона хорошо подходит для параллельных вычислений. [5] Алгоритм тесно связан с алгоритмами аукциона для других задач сетевого потока. [5] Согласно вычислительным экспериментам, алгоритм аукциона, как правило, уступает другим современным алгоритмам для задачи поиска кратчайшего пути для всех пунктов назначения, но очень быстр для задач с небольшим количеством пунктов назначения (существенно больше одного и существенно меньше общего числа узлов); см. статью Берцекаса, Паллоттино и Скутеллы «Алгоритмы полиномиального аукциона для кратчайших путей».
Алгоритмы аукциона для задач на кратчайший гиперпуть были определены Де Леоне и Претолани в 1998 году. Это также параллельный алгоритм аукциона для взвешенного двудольного сопоставления, описанный Э. Джейсоном Риди в 2004 году. [6]
(Последовательные) алгоритмы аукциона для задачи поиска кратчайшего пути были предметом экспериментов, которые были описаны в технических статьях. [7] Эксперименты ясно показывают, что алгоритм аукциона уступает современным алгоритмам поиска кратчайшего пути для поиска оптимального решения задач с одним источником и всеми пунктами назначения. [7]
Хотя в алгоритме аукциона общая выгода монотонно увеличивается с каждой итерацией, в венгерском алгоритме (из Kuhn, 1955; Munkres, 1957) общая выгода строго увеличивается с каждой итерацией.
Считается, что аукционный алгоритм Берцекаса для поиска кратчайших путей в ориентированном графе очень хорошо работает на случайных графах и в задачах с небольшим количеством пунктов назначения. [5]