근사 알고리즘/Network design (2) 썸네일형 리스트형 슈타이너 포레스트 & 고먼스-윌리엄슨 알고리즘 (Steiner Forest & Goemans-Williamson Algorithm) 여러분이 큰 규모의 네트워크를 설계하는 업무를 맡게 되었다고 해 봅시다. 네트워크란 결국 특정한 단말들 사이의 통신을 보장하는 구조를 일컬으며, 따라서 여러분의 목표는 연결이 필요한 단말의 쌍들이 주어졌을 때, 최소의 비용으로 이들을 모두 연결시키는 네트워크를 구성하는 것이 되겠습니다. 참고로 구성된 네트워크 전체가 하나로 연결될 필요는 없습니다. 그저 주어지는 단말 쌍들의 연결만 보장되면 됩니다. 어떻게 구성하면 좋을까요? 네트워크 설계(network design) 분야에서 매우 유명한 이 문제의 이름은 일반화된 슈타이너 트리(generalized Steiner tree) 혹은 슈타이너 포레스트(Steiner forest) 문제입니다. 이름에서 유추할 수 있듯이 이 문제는 저번에 공부한 슈타이너 트리 .. 슈타이너 트리 2-근사 알고리즘 (2-Approximation for Steiner Tree) 코스워크가 모두 끝난 요즘 과거에 제대로 이해하지 못했거나 미처 보지 못하고 넘어간 것들을 제대로 공부해 보고자 교과서를 처음부터 다시 보고 있습니다. 공부하는 중에 개인적으로 정리도 할 겸 공유할 만한 내용이 있으면 포스팅을 하고자 합니다. 이번에 다룰 문제는 슈타이너 트리 문제(Steiner tree problem)입니다. 이 문제는 잘 알려진 최소 스패닝 트리 문제(minimum spanning tree problem, MST)의 일반화된 문제입니다. MST는 크루스칼 알고리즘(Kruskal's algorithm)이나 프림 알고리즘(Prim's algorithm) 등을 활용하여 다항 시간에 해결할 수 있다는 것이 잘 알려져 있습니다. 하지만 슈타이너 트리 문제는 NP-난해(NP-hard)하다고 알려.. 이전 1 다음
