옥션 알고리즘

Auction algorithm
알고리즘 경매와 혼동하지 말 것.
다음에 대한 시리즈 일부
경매
Auction Room, Christie's, circa 1808.
종류들
입찰
컨텍스트
이론
온라인.

"흡입 알고리즘"[1]이라는 용어는 할당 문제를 해결하는 조합 최적화 알고리즘과 선형 및 볼록/비선형 비용의 네트워크 최적화 문제에 적용된다.경매 알고리즘은 여러 구매자에게 제공되는 일련의 제품에서 가장 좋은 가격을 결정하기 위해 사업 환경에서 사용되어 왔다.반복적인 절차인 만큼 '옥션 알고리즘'이라는 명칭은 경매 경매와 관련이 있는데, 이 경매에서 복수의 입찰을 비교하여 최적의 매물을 결정하는 것으로 최종 매물이 최고 입찰자에게 돌아간다.

경매 알고리즘의 원래 형태는 최적의 가격을 찾기 위한 반복적인 방법과 최대 중량 매칭 문제(MWM)인 초당적 그래프에서 순 편익을 최대화하는 과제다.[2][3]이 알고리즘은 1979년 디미트리 베르체카스에 의해 처음 제안되었다.

경매 알고리즘과 ε-스케일링의[1] 아이디어는 단일 상품 선형 네트워크 흐름 문제에 대한 프리플로-푸시 알고리즘에서도 중심적이다.실제로 최대유량에 대한 프리플로-푸시 알고리즘은 재조정 후 최대유량 문제에 원래의 1979년 경매 알고리즘을 적용하여 할당문제로 도출할 수 있다.더욱이 선형 최소비용 흐름 문제에 대한 프리플로우-푸시 알고리즘은 수학적으로 ε-relaxation 방법과 동일하며, 이 알고리즘은 문제가 등가 할당 문제로 개편된 후 원래의 경매 알고리즘을 적용하여 얻는다.[4]

이후 최단 경로 문제를 해결하는 경매 알고리즘의 변형이 1991년에 베르체카스에 의해 도입되었다.[5]지시된 그래프에서 최단 경로를 찾기 위한 간단한 알고리즘이다.단일 출발지/단일 도착지 사례에서 경매 알고리즘은 출발지에서 시작하는 단일 경로를 유지하며, 각 반복에서 단일 노드에 의해 확장되거나 수축된다.동시에, 이중 함수의 값을 개선하거나 유지하기 위해 각 반복마다 최대 하나의 이중 변수가 조정될 것이다.복수 기원의 경우 경매 알고리즘은 병렬 연산에 적합하다.[5]알고리즘은 다른 네트워크 흐름 문제에 대한 경매 알고리즘과 밀접하게 관련되어 있다.[5]컴퓨터 실험에 따르면, 경매 알고리즘은 일반적으로 모든 목적지 최단 경로 문제에 대해 다른 최첨단 알고리즘에 비해 열악하지만, 목적지가 거의 없는 문제(실질적으로 1개 이상이고 총 노드 수보다 실질적으로 적다)에는 매우 빠르다; 베르체카스, 팔로티노, 팰로티노의 기사를 참조하라.스쿠텔라, 최단 경로를 위한 다항식 경매 알고리즘.

최단 하이퍼패스 문제에 대한 경매 알고리즘은 1998년 De Leone과 Pretolani에 의해 정의되었다.이것은 또한 가중 양당 매칭을 위한 병렬 경매 알고리즘으로, 2004년에 E. Jason Redy가 기술했다.[6]

비교

최단 경로 문제에 대한 (순차적인) 경매 알고리즘은 기술 논문에서 보고된 실험의 주제였다.[7]실험 결과, 경매 알고리즘이 단발성 문제의 최적 해결책을 찾기 위한 최첨단 최단 경로 알고리즘보다 열등하다는 것을 분명히 알 수 있다.[7]

경매 알고리즘을 사용하면 총 이득은 단조롭게 각 반복에 따라 증가하지만, 헝가리 알고리즘(Kuhn, 1955; Munkres, 1957)에서는 총 이득이 각 반복에 따라 엄격하게 증가한다.

지시된 그래프 내에서 최단 경로를 찾기 위한 베르체카스의 경매 알고리즘은 무작위 그래프와 목적지가 거의 없는 문제에서 매우 잘 수행된다고 알려져 있다.[5]

참고 항목

참조

  1. ^ a b 디미트리 P. 베르체카스."배정 문제에 대한 분산 알고리즘", 원본, 1979년.
  2. ^ M.G. 레센데, P.M. 파르달로스."통신 최적화 핸드북", 2006
  3. ^ M. Bayati, D.샤, 샤르마."A Simple Max-Product Max Weight Match Malk Matching Algorithm and the A 옥션 알고리즘", 2006, 웹 페이지 PDF: MIT-bpmwm-PDF Archived 2017-09-21 Wayback Machine.
  4. ^ 디미트리 P.베르체카스."선형 네트워크 흐름 문제를 위한 분산된 이완 알고리즘," 25번째 IEEE CDC, 아테네, 그리스, 1986, 페이지 2101-2106, IEEXplore에서 온라인으로 제공[1]
  5. ^ a b c d 디미트리 P.베르체카스."최단 경로 경매 알고리즘", SIAM 최적화 저널, 1:425—447, 1991, PSU-bertsekas91ation
  6. ^ 2004년 2월, UC 버클리 E. Jason Redy, E. Jason Redy, UC Berkeley [2].
  7. ^ a b 첫 번째 저자가 웨이백 머신(1997)에서 보관한 2011-06-05의 최단 경로에 대한 경매 알고리즘의 실제 성능에 대한 참고 사항도 참조하십시오Larsen, Jesper; Pedersen, Ib (1999). "Experiments with the auction algorithm for the shortest path problem". Nordic Journal of Computing. 6 (4): 403–42. ISSN 1236-6064..

외부 링크

  • 디미트리 P.베르체카스."선형 네트워크 최적화", MIT 프레스, 1991년 온라인.
  • 디미트리 P.베르체카스."네트워크 최적화:연속형 및 이산형 모델", Athena Scientific, 1998.
  • 디미트리 P.베르체카스."최단 경로에 대한 경매 알고리즘", SIAM 최적화 저널, 1:425—447, 1991, 웹페이지: PSU-bertsekas91ation.
  • D.P. 버체카스, S. 팔로티노, M. G. 스쿠텔라."최단 경로를 위한 다항식 경매 알고리즘," , 계산 최적화 및 응용 프로그램, Vol. 4, 1995, 페이지 99-125.
  • Florian Bernard에 의한 Matlab에서 Bertsekas의 옥션 알고리즘 구현, 웹페이지:Matlab 파일 교환.