조합론적 최적화/Matching (9) 썸네일형 리스트형 안정 매칭 (Stable Matching) 오랜만에 글을 적습니다. 미국에서 인턴을 마치고 돌아온 후 그동안 좀 바빴습니다. 인턴을 하는 동안 연구한 결과를 잘 마무리하여 학회에 제출하기도 했고, 이론 컴퓨터 과학을 연구하거나 그것에 관심이 있는 학생들을 모아 교내 학생 모임을 발족하기도 하였습니다. 모쪼록 좋은 결과가 있기를 바라 봅니다. 그러는 와중에 최근 흥미로운 논문을 하나 읽었습니다. 지난 포스트에서 다루었던 다중 슬롯머신 문제(multi-armed bandits)에다가 안정 매칭(stable matching)을 결합한 문제였습니다. 다중 슬롯 머신이 무엇인지 궁금하시면 아래 포스트를 참고하시기 바랍니다. 다중 슬롯머신 문제 & 비적응 탐사 알고리즘 (Multi-Armed Bandits & Non-Adaptive Exploration A.. 경제학으로 해석한 헝가리안 알고리즘 할당 문제(assignment problem)는 \(n\) 명의 노동자와 \(n\) 개의 작업 그리고 각 노동자를 각 작업에 할당했을 때 발생하는 비용이 모두 주어졌을 때, 각 노동자를 하나의 작업에 중복 없이 모두 최소의 비용으로 할당하는 방법을 찾는 문제이며, 헝가리안 알고리즘(Hungairan algorithm)은 이 문제를 해결하는 가장 유명한 방법입니다. 할당 문제와 헝가리안 알고리즘은 조합론적 최적화(combinatorial optimization) 분야의 근간을 이루는 개념 중 하나일 뿐 아니라 산업 공학(industrial engineering), 운용 과학(operations research) 등 여러 실용적인 분야에서도 널리 활용됩니다. 이렇게 다양한 분야에서 활약하는 할당 문제와 헝가.. 세제곱 시간 헝가리안 알고리즘 (Hungarian Algorithm in Cubic Time) 할당 문제(assignment problem)는 \(n\) 명의 노동자와 \(n\) 개의 작업이 주어지고, 각 노동자-작업 쌍마다 노동자를 작업에 할당할 때의 비용이 주어질 때, 최소의 비용으로 각 노동자를 작업에 하나씩 할당하는 방법을 찾는 문제입니다. 제 블로그에는 할당 문제와 이를 해결하는 알고리즘인 헝가리안 알고리즘(Hungarian algorithm)에 대해 정리한 글이 있습니다. 제 블로그에서 가장 인기가 있는 글이죠. 2019.08.07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm.. 텃의 정리 (Tutte's Theorem) 드넓은 황야에 위치한 초원 대학교의 컴퓨터과학과 소속 폰가젤 교수는 2인 조별 과제를 내는 것을 좋아합니다. 혼자서 해결하기에는 벅찬 문제를 두 명이서 협력하여 해결한다면 학생들에게 협동심은 물론 위기에 굴복하지 않는 능력을 기를 수 있다고 굳게 믿기 때문이죠. 물론 '조별과제 잔혹사'라는 말을 언젠간 들어 봤을 정도로 학생들의 원성이 자자하다는 사실도 잘 알고 있습니다. 그가 개설했던 알고리즘 수업의 강의 평가를 보면 쉽게 유추할 수 있었죠. 그동안은 학생들이 자율적으로 조를 편성하도록 놔두었는데, 이러니 어떤 학생들은 전혀 마음이 맞지 않는 사람과 조를 이루어야 하는 불상사가 발생했었죠. 이 부분이 바로 학생들이 가장 불편을 느낀 부분이었습니다. 이번 학기에 가젤 교수는 이러한 학생들의 원성을 잠재우.. 헝가리안 알고리즘 시간 복잡도 분석 지난번에 할당 문제와 헝가리안 알고리즘을 주제로 글을 작성하였습니다. 아래 링크를 참조하세요. 2019/08/07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 이번 포스팅에서는 assignment problem과 Hungarian algorithm에 대해서 알아보겠습니다. 먼저 assignment problem이 어떤 것인지에 대해서 살펴보고, 이를 해결하는 방법을 알아보도록 하겠습니다. 인터넷을 찾아.. gazelle-and-cs.tistory.com 저기서는 할당 문제가 무엇인지 알아보고.. 호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm) 엄청 오랜만에 포스팅을 합니다. 방학이 되면 시간이 나서 글을 좀 쓸 수 있을 줄 알았는데, 대학원생은 방학도 바쁘군요. 다행히 어느정도 일단락이 나서 이렇게 글을 쓸 수 있게 되었습니다. 개강 전에 한 두 개는 더 적을 수 있지 않을까 생각합니다. 반년에 글 하나씩 올리는 주제에 블로그를 운영한다고 말할 수 있으련지는 모르겠지만, 아무튼 블로그를 운영하면서 이제 슬슬 외부에도 노출이 되어가는 것을 보니 감회가 새롭습니다. 특히 제 블로그에서 가장 조회수가 높은 글은 헝가리안 알고리즘에 관한 글이었습니다. 2019/08/07 - [조합론적 최적화/Bipartite matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 .. 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 이번 포스팅에서는 assignment problem과 Hungarian algorithm에 대해서 알아보겠습니다. 먼저 assignment problem이 어떤 것인지에 대해서 살펴보고, 이를 해결하는 방법을 알아보도록 하겠습니다. 인터넷을 찾아보니 Hungarian algorithm 자체가 어떻게 동작하는지에 대해서는 우리말로 된 포스팅이 많이 있는 반면에 이 알고리즘이 왜 정확히 돌아가는지에 대해서 분석한 글은 보지 못하였습니다. 제 블로그는 이 간격을 열심히 줄이는 데 초점이 맞추어져 있습니다. 그러니 이번에도 왜 이 알고리즘이 올바른 결과를 출력하는지 함께 알아보도록 하죠. 문제 정의 문제를 정의하기 전에 제 하소연부터 좀 하겠습니다. 이 글을 작성하는 현재 제 자취방 에어컨이 고장 난 상태입니다.. 쾨니그의 정리 (Kőnig's Theorem) 이 글은 홀의 정리 (Hall's Theorem)와 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요.2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem) 무언가를 최적화시키는 문제를 보면 생각보다 많은 경우 다른 최적화 문제와 크게 관련이 있는 것을 볼 수 있습니다. 대표적인 예시가 바로 최대유량 최소컷 정리(maximum flow minimum cut theorem)입니다. 이 정리에 따르면, 어떤 flow network에서 유량(flow)을 최대화하는 문제는 곧 그 network의 최소 컷(cut)을 찾는 문제와 동일하다는 사실을 알 수 있습니다.. 이번에 함께 살펴 볼 문제들도 이와 비슷한 관계가 있습니다. 바로 matching과 vertex cover입니.. 홀의 정리 (Hall's Theorem) 여러분이 어떤 단체의 인사 담당자라고 하죠. 총 다섯 명의 직원이 새로이 자리를 배치 받아야 하는 상황입니다. 고맙게도 충원되어야 하는 자리도 총 다섯 개입니다. 자애로운 여러분은 모든 직원들이 만족하도록 자리를 배치하고 싶어서 직원들에게 자신이 배치 받아도 좋은 자리가 어딘지를 먼저 물어 보았습니다. 직원은 알파벳(A-E)으로, 자리는 숫자(1-5)로 표현했을 때, 여러분은 직원들이 원하는 자리를 다음과 같이 표현하였습니다.이제 여러분은 직원들에게 자리를 배치해야 합니다. 아마도 여러분은 다음 그림과 같이 손쉽게 네 명은 배치할 수 있을 것입니다. 실제로 배치된 것을 빨간 실선으로 표현하였습니다.하지만 직원 E를 배치하지 못한 상황입니다. 과연 여러분은 모든 직원에게 서로 다른 자리를 하나씩 배치할 수.. 이전 1 다음
