근사 알고리즘/Facility location (4) 썸네일형 리스트형 설비 입지 선정 원-쌍대 근사 알고리즘 (Primal-Dual Approximation Algorithm for Facility Location) 지난 포스트에서 우리는 설비 후보지들이 주어질 때 최소의 비용으로 몇 곳의 후보지에 설비를 지어 모든 고객을 서비스하는 방법을 찾는 설비 입지 선정 문제(facility location problem)를 공부하였습니다. 언뜻 보기에도 산업적으로 유용해 보이는 이 문제는 이론적으로도 흥미로운 부분이 많아서 널리 연구가 되었습니다. 지난 포스트에서는 그중에서도 특히 이 문제를 해결하는 4-근사 알고리즘을 배웠습니다. 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설 gazelle-and-cs.tistory.. 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설해야 하겠죠. 여러 곳에서 자문을 얻어 물류 창고를 건설할 후보지를 받아 놓았다고 합시다. 이제 여러분은 큰 결단의 기로에 서게 됩니다. 바로 후보지 중 어느 곳에 물류 창고를 건설할지 결정해야 합니다. 고려해야 하는 요인은 크게 두 가지입니다. 하나는 각 후보지마다 물류 창고를 건설하게 될 때 발생할 비용일 것이고, 다른 하나는 물류 창고에서 각 고객에게 상품을 배송할 때 들어가는 비용입니다. 경영자의 입장에서 여러분은 당연히 총 비용이 최소가 되도록 하고 싶습니다. 과연 어느 후보지에 물류 창고를 건설하면 될까요? 실제 .. [k-Center Problem] 2-근사 알고리즘 오랜만에 포스팅을 합니다. 아무래도 학기가 시작하니 글을 쓸 시간도, 마음도 나지 않는 것 같네요. 그래도 시작한 \(k\)-center problem은 끝은 봐야겠다 싶어서 써 봅니다. 지난 포스트에서는 이 문제가 어떤 것인지 정의를 했습니다. 여러 곳에서 어떤 장비가 필요한데, 그 장비를 각 장소에 하나씩 배치하지 못하는 경우, 가장 공정하게 장비를 배치하는 방법에 관한 문제였습니다. \(k\)-center problem 지점의 집합 \(V\)와 거리 \(d : V \times V \rightarrow \mathbb{Q}_{\geq 0}\) 그리고 자연수 \(k\)가 주어졌을 때, \(|S| \leq k\)이면서 \[ \tau_S := \max_{v \in V} d(S, v)\]를 최소화하는 \(S .. [k-Center Problem] 문제 정의 이번에 다룰 주제는 \(k\)-center problem입니다. 이 문제는 입력된 자료들을 몇 개의 덩어리로 묶음을 짓는 군집화(clustering) 문제 중 하나입니다. 군집화를 할 때 사용하는 상황이나 목적에 따라 어떤 군집이 좋고 나쁜지를 판가름하는 척도가 달라지게 될 것입니다. 이 문제의 목표는 최대한 공정하게 덩어리 짓는 방법을 찾는 것입니다. 다음 예시를 통해서 이 문제의 목표가 무엇인지 자세히 살펴보도록 하죠. 들어가기 자, 여러분이 회사를 하나 경영하고 있다고 하죠. 회사가 규모가 커서 다음 그림처럼 곳곳에 지부가 있다고 합시다. 이번에 사업을 확장하게되어 고가의 장비를 들여오게 되었습니다. 이 장비는 모든 지부의 부서들이 이용할 만큼 매우 요긴한 것이죠. 다만, 하도 가격이 비싸다보니 모.. 이전 1 다음
