최신 글
-
Network design
슈타이너 포레스트 & 고먼스-윌리엄슨 알고리즘 (Steiner Forest & Goemans-Williamson Algorithm)
여러분이 큰 규모의 네트워크를 설계하는 업무를 맡게 되었다고 해 봅시다. 네트워크란 결국 특정한 단말들 사이의 통신을 보장하는 구조를 일컬으며, 따라서 여러분의 목표는 연결이 필요한 단말의 쌍들이 주어졌을 때, 최소의 비용으로 이들을 모두 연결시키는 네트워크를 구성하는 것이 되겠습니다. 참고로 구성된 네트워크 전체가 하나로 연결될 필요는 없습니다. 그저 주어지는 단말 쌍들의 연결만 보장되면 됩니다. 어떻게 구성하면 좋을까요? 네트워크 설계(network design) 분야에서 매우 유명한 이 문제의 이름은 일반화된 슈타이너 트리(generalized Steiner tree) 혹은 슈타이너 포레스트(Steiner forest) 문제입니다. 이름에서 유추할 수 있듯이 이 문제는 저번에 공부한 슈타이너 트리 ..
-
연습 노트
독립 집합에 관한 노트
작년 말부터 올해 초까지 있었던 일입니다. 학교 동료한테서 소개 받은 문제를 고민하던 차에 굉장한 아이디어가 떠올라서 그 문제를 뚝딱 풀어버렸습니다. 너무 기쁜 나머지 문제를 소개해 준 동료는 물론 지도 교수님을 포함한 여러 사람들에게 이 사실을 널리 알리고 다녔죠. 주변 사람들도 그럴듯하다며 인정해 주었습니다. 며칠이 지났을까, 불현듯 그 증명에서 가장 핵심적인 단계가 참이 아닐 수도 있겠다는 의구심이 들었고, 조금 고민해 보니 정말 틀렸더군요. 한동안 주위 사람들에게 제 증명이 사실은 틀렸다고 말하고 다니느라 멋쩍은 시간을 보냈습니다. 이렇게 언뜻 보기에는 참일 것 같은 명제에 반례를 발견하게 되면 개인적으로 이를 블로그에 정리합니다. 스스로를 위한 비망록이면서도 혹 누군가가 비슷한 고민을 할 때 소..
-
Delayed TCP acknowledgement
지연된 TCP 확인응답 (Delayed TCP Acknowledgement)
전송 제어 프로토콜(transmission control protocol, 이하 TCP)은 현대의 네트워크를 구성하는 가장 핵심적인 규약으로, 패킷이 전송된 후 전송이 성공적으로 완료되었음을 알려주는 확인응답(acknowledgement, 이하 ACK)을 다시 보내는 방식으로 전송의 신뢰성을 보장합니다. 그런데 만약 패킷이 전송될 때마다 ACK를 보내게 된다면, 가뜩이나 복잡한 네트워크에 큰 부하를 추가로 줄 것이 뻔합니다. 이를 회피하기 위해서 TCP에는 패킷이 전송되었을 때 바로 ACK를 보내지 않고 다른 패킷이 전송되는 것을 기다렸다가 적절한 때에 지금껏 들어온 패킷들에 대한 ACK를 한 번에 처리하는 기술이 있습니다. 이를 지연된 확인응답(delayed acknowledgement)이라고 부릅니다..
-
Online matching
온라인 이분 매칭 경쟁비 상한 (Upper Bound of Competitive Ratio for Online Bipartite Matching)
지난 시간에 우리는 온라인 분수 이분 매칭 문제(online fractional bipartite matching problem)를 \(1-1/e \approx 0.632\)의 경쟁비로 해결하는 결정론적 알고리즘(deterministic algorithm)인 물 채우기 알고리즘(water-filling algorithm)을 공부하였습니다. 온라인 분수 이분 매칭 (Online Fractional Bipartite Matching) 우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 gazelle-and-cs.tistory.com 아래 본문의 정의와 기호는 이전 글의 것과 동..
-
Online matching
온라인 분수 이분 매칭 (Online Fractional Bipartite Matching)
우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 수 있는 기계를 몇 대 갖고 있습니다. 문제는 각 작업마다 해당 작업을 처리할 수 있는 기계가 따로 정해져 있다는 것이며, 심지어 어느 기계에서 처리될 수 있는지는 해당 작업이 도착해야 알 수 있다는 점입니다. 우리는 매번 작업이 도착할 때마다 이 작업을 어떤 기계에 할당할지, 그리고 만약 할당한다면, 어느 가용한 기계에 할당하여 줄지를 바로 결정하여야 합니다. 여기서 어려운 점은 이 결정을 후일 번복할 수 없다는 것입니다. 이런 환경에서 작업이 모두 도착했을 때 최대한 많은 작업을 처리하는 것이 목표입니다. 이는 유명한 ..
