근사 알고리즘 (15) 썸네일형 리스트형 슈타이너 포레스트 & 고먼스-윌리엄슨 알고리즘 (Steiner Forest & Goemans-Williamson Algorithm) 여러분이 큰 규모의 네트워크를 설계하는 업무를 맡게 되었다고 해 봅시다. 네트워크란 결국 특정한 단말들 사이의 통신을 보장하는 구조를 일컬으며, 따라서 여러분의 목표는 연결이 필요한 단말의 쌍들이 주어졌을 때, 최소의 비용으로 이들을 모두 연결시키는 네트워크를 구성하는 것이 되겠습니다. 참고로 구성된 네트워크 전체가 하나로 연결될 필요는 없습니다. 그저 주어지는 단말 쌍들의 연결만 보장되면 됩니다. 어떻게 구성하면 좋을까요? 네트워크 설계(network design) 분야에서 매우 유명한 이 문제의 이름은 일반화된 슈타이너 트리(generalized Steiner tree) 혹은 슈타이너 포레스트(Steiner forest) 문제입니다. 이름에서 유추할 수 있듯이 이 문제는 저번에 공부한 슈타이너 트리 .. 설비 입지 선정 원-쌍대 근사 알고리즘 (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이 (우리말로 외판원 문제) 무엇인지 알아보았습니다. 안타깝게도 일반적인 거리에 대해.. 이전 1 2 다음
