근사알고리즘 (5) 썸네일형 리스트형 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설해야 하겠죠. 여러 곳에서 자문을 얻어 물류 창고를 건설할 후보지를 받아 놓았다고 합시다. 이제 여러분은 큰 결단의 기로에 서게 됩니다. 바로 후보지 중 어느 곳에 물류 창고를 건설할지 결정해야 합니다. 고려해야 하는 요인은 크게 두 가지입니다. 하나는 각 후보지마다 물류 창고를 건설하게 될 때 발생할 비용일 것이고, 다른 하나는 물류 창고에서 각 고객에게 상품을 배송할 때 들어가는 비용입니다. 경영자의 입장에서 여러분은 당연히 총 비용이 최소가 되도록 하고 싶습니다. 과연 어느 후보지에 물류 창고를 건설하면 될까요? 실제 .. 동일한 기계 여러 대에 작업 할당하기 (Load Balancing on Identical Machines) 여러분이 어떤 작업들을 처리해야 한다고 해봅시다. 작업들은 특수한 기계에 의해 처리되며, 여러분은 동일한 성능을 가진 기계를 여러 대 받았습니다. 작업들 사이에는 선후행 관계가 없습니다. 다시 말해, 어떤 작업을 처리하기 위해서 다른 어떤 작업이 처리되어야 한다는 식의 조건은 존재하지 않습니다. 당연히 여러분은 일을 빨리 끝내고 싶어 합니다. 과연 어떻게 작업을 기계에 할당해야 할까요? 만약 모든 작업이 수행되는 시간이 동일하면 이 문제는 쉽게 해결됩니다. 작업의 개수를 \(n\), 기계의 대수를 \(m\)이라고 했을 때, 각 기계마다 최대 \( \lceil n/m \rceil \) 개씩 넣어주면 되겠습니다. 모든 작업이 끝나는 시각이 이보다 빠를 수 없다는 것은 비둘기집 원리를 사용하면 쉽게 증명할 수.. 슈타이너 트리 2-근사 알고리즘 (2-Approximation for Steiner Tree) 코스워크가 모두 끝난 요즘 과거에 제대로 이해하지 못했거나 미처 보지 못하고 넘어간 것들을 제대로 공부해 보고자 교과서를 처음부터 다시 보고 있습니다. 공부하는 중에 개인적으로 정리도 할 겸 공유할 만한 내용이 있으면 포스팅을 하고자 합니다. 이번에 다룰 문제는 슈타이너 트리 문제(Steiner tree problem)입니다. 이 문제는 잘 알려진 최소 스패닝 트리 문제(minimum spanning tree problem, MST)의 일반화된 문제입니다. MST는 크루스칼 알고리즘(Kruskal's algorithm)이나 프림 알고리즘(Prim's algorithm) 등을 활용하여 다항 시간에 해결할 수 있다는 것이 잘 알려져 있습니다. 하지만 슈타이너 트리 문제는 NP-난해(NP-hard)하다고 알려.. [외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm) 지난 포스팅에서 traveling salesman problem이 (우리말로 외판원 문제) 무엇인지 알아보았습니다. 안타깝게도 일반적인 거리에 대해서는 적절한 근사 알고리즘이 존재하기 어렵다는 것을 보였습니다. 하지만 metric인 경우에는 2-근사 알고리즘이 존재한다는 것을 보였습니다. 아직 보지 않으셨다면 다음 링크를 참조해 주세요. :) 2019/07/20 - [근사 알고리즘/Traveling salesman problem] - [Traveling Salesman Problem] Metricity & 2-Approximation [외판원 문제 / Traveling Salesman Problem] 메트릭 & 2-근사 (Metricity & 2-Approximation) 안녕하세요. 이번에는 trave.. 근사 알고리즘 (Approximation Algorithm) 현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요? 아시는 분들은 아시겠지만, 컴퓨터가 모든 것을 해결해 줄 수는 없습니다. 가장 유명한 예시로는 halting problem이 있습니다. 이는 어떤 컴퓨터 프로그램과 그 프로그램의 한 입력이 주어졌을 때, 프로그램이 언젠간 끝이 나는지 아니면 영원히 동작할지를 판단하는 문제입니다. 저명한 수학자 Alan Turing은 이 문제가 컴퓨터로는, 좀 더 정확히는 Turing machine으로는, 해결할 수 없다는 것을 증명하였습니다. 이번에는 약간 결이 다른 이야기를 해보겠습니다. 여러분들이 유명 밴드의 매니저.. 이전 1 다음
