근사 알고리즘 (14) 썸네일형 리스트형 설비 입지 선정 원-쌍대 근사 알고리즘 (Primal-Dual Approximation Algorithm for Facility Location) 지난 포스트에서 우리는 설비 후보지들이 주어질 때 최소의 비용으로 몇 곳의 후보지에 설비를 지어 모든 고객을 서비스하는 방법을 찾는 설비 입지 선정 문제(facility location problem)를 공부하였습니다. 언뜻 보기에도 산업적으로 유용해 보이는 이 문제는 이론적으로도 흥미로운 부분이 많아서 널리 연구가 되었습니다. 지난 포스트에서는 그중에서도 특히 이 문제를 해결하는 4-근사 알고리즘을 배웠습니다. 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설 gazelle-and-cs.tistory.. 상관없는 기계에서 가중치 완성 시간 최소화하기 (Minimizing Weighted Completion Time on Unrelated Machines) 한 회사에서 어떤 작업들을 처리해야 한다고 합시다. 이 작업들을 처리하기 위해 기계 수 대를 갖고 있습니다. 각 기계들은 회사가 성장해 가면서 하나씩 사들이는 바람에 제원이나 사양이 모두 다릅니다. 다만, 모든 기계는 한 번에 하나의 작업만을 처리할 수 있으며, 한 작업이 시작되면 이를 중단하지 않고 끝까지 처리합니다. 회사 내에서 거의 유일하게 머리 좀 쓰는 공돌이인 여러분은 기계를 활용하여 작업들을 적절히 처리하라는 지시를 받았습니다. 지시 사항을 전달 받은 여러분은 상사에게 곧장 되물었습니다. 목표가 무엇인가요? 기계의 수행 시간을 최소화해야 하는지, 마감 기한을 어기는 정도를 최소화해야 하는지, 아니면 전기비 절감을 위해 기계가 사용하는 에너지를 최소화해야 하는지 등 작업 스케줄을 평가하는 요소는.. 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설해야 하겠죠. 여러 곳에서 자문을 얻어 물류 창고를 건설할 후보지를 받아 놓았다고 합시다. 이제 여러분은 큰 결단의 기로에 서게 됩니다. 바로 후보지 중 어느 곳에 물류 창고를 건설할지 결정해야 합니다. 고려해야 하는 요인은 크게 두 가지입니다. 하나는 각 후보지마다 물류 창고를 건설하게 될 때 발생할 비용일 것이고, 다른 하나는 물류 창고에서 각 고객에게 상품을 배송할 때 들어가는 비용입니다. 경영자의 입장에서 여러분은 당연히 총 비용이 최소가 되도록 하고 싶습니다. 과연 어느 후보지에 물류 창고를 건설하면 될까요? 실제 .. 다품종 정수 흐름 (Multicommodity Integeral Flows) 최대 흐름 문제(maximum flow problem)은 유명한 조합론적 최적화 문제 중 하나입니다. 이 문제는 시점과 종점이 있는 어떤 흐름 네트워크(flow network)가 주어졌을 때, 최대한 많은 양의 유체를 시점에서 종점으로 흘리는 방법을 찾는 문제입니다. 자세한 내용은 이전 포스트에서 정리하였으니 궁금하신 분은 참조하시기 바랍니다. 2020/08/29 - [조합론적 최적화/Flow & Circulation] - 최대 흐름 문제 이해하기 (Maximum Flow Problem) 최대 흐름 문제 이해하기 (Maximum Flow 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)하다고 알려.. [배낭문제 / Knapsack Problem] 다항 시간 근사 해법 (PTAS) 지난 포스트에서는 유명한 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(knapsack problem)에 대해서 공부하였습니다. 어떤 문제인지 다시 정의하자면, 우리에게는 물건의 집합 \(I = \{1, \cdots, n\}\)와 배낭의 최대 하중 \(B \in \mathbb{Z}_+ \)가 주어집니다. 각각의 물건 \(i \in I\)에도 무게 \(w_i \in \mathbb{Z}_+\)와 가치 \( v_i \in \mathbb{Z}_+\)가 함께 주어집니다. 여기서 지난 시간과는 달리, 입력으로 주어지는 값 \(Z, w_i, v_i\) 모두가 (음이 아닌) 정수라는 가정을 하도록 하겠습니다.[ㄱ] 또한 어차피 무게가 \(B\)를 넘으면 가방에 담을 수도 없으니 무게가 \(B\)를 넘는 물건은 .. [배낭문제 / Knapsack Problem] 0.5-근사 알고리즘 약간 발칙한 상상을 해봅시다. 여러분은 도둑이고 고가의 귀중품을 훔치기 위해 한 가게에 들어와 있습니다. 여러분의 눈앞에는 보기만 해도 휘황찬란한 물건들이 진열되어 있습니다. 당연히 모두 챙길 수 있다면 가장 좋을 겁니다. 하지만 이 물건들을 들고 가는 방법은 오직 여러분의 등에 매달린 배낭을 사용하는 것 뿐입니다. 배낭에는 최대로 견딜 수 있는 하중이 정해져 있고, 이를 초과하여 물건을 담는다면 배낭이 찢어져 버립니다. 배낭을 못 쓰게 된다면 손에 몇 개 쥐고 나오는 것 밖에는 방법이 없으니 큰 손해임이 분명합니다. 따라서 여러분의 목표는 배낭이 찢어지지 않을 정도의 무게로 가장 가치있는 물건들을 선택하는 것이 되겠죠. 이 문제가 바로 잘 알려진 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(k.. 크리스토피데스 알고리즘으로 경로 외판원 문제 풀기 (Path TSP by Christofides' Algorithm) 오랜만에 근사 알고리즘으로 돌아왔습니다. 지난번 크리스토피데스 알고리즘(Christofides' algorithm)을 공부하면서 마지막에 외판원 문제(traveling salesman problem, TSP)의 변형인 경로 외판원 문제(path TSP)를 소개하면서 끝냈습니다. 2019/07/23 - [근사 알고리즘/Traveling salesman problem] - [외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm) [외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm) 지난 포스팅에서 traveling salesman 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 .. 이전 1 2 다음
