Gazelle and Computer Science

최신 글

• 

  연습 노트 독립 집합에 관한 노트 작년 말부터 올해 초까지 있었던 일입니다. 학교 동료한테서 소개 받은 문제를 고민하던 차에 굉장한 아이디어가 떠올라서 그 문제를 뚝딱 풀어버렸습니다. 너무 기쁜 나머지 문제를 소개해 준 동료는 물론 지도 교수님을 포함한 여러 사람들에게 이 사실을 널리 알리고 다녔죠. 주변 사람들도 그럴듯하다며 인정해 주었습니다. 며칠이 지났을까, 불현듯 그 증명에서 가장 핵심적인 단계가 참이 아닐 수도 있겠다는 의구심이 들었고, 조금 고민해 보니 정말 틀렸더군요. 한동안 주위 사람들에게 제 증명이 사실은 틀렸다고 말하고 다니느라 멋쩍은 시간을 보냈습니다. 이렇게 언뜻 보기에는 참일 것 같은 명제에 반례를 발견하게 되면 개인적으로 이를 블로그에 정리합니다. 스스로를 위한 비망록이면서도 혹 누군가가 비슷한 고민을 할 때 소..

• 

  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) 우리에게 처리해야 할 작업들이 있다고 해 보겠습니다. 다만 작업들은 처음부터 주어지지 않고 시간이 흐르면서 하나씩 도착합니다. 작업을 처리하기 위해 우리는 최대 하나의 작업을 할당받을 수 있는 기계를 몇 대 갖고 있습니다. 문제는 각 작업마다 해당 작업을 처리할 수 있는 기계가 따로 정해져 있다는 것이며, 심지어 어느 기계에서 처리될 수 있는지는 해당 작업이 도착해야 알 수 있다는 점입니다. 우리는 매번 작업이 도착할 때마다 이 작업을 어떤 기계에 할당할지, 그리고 만약 할당한다면, 어느 가용한 기계에 할당하여 줄지를 바로 결정하여야 합니다. 여기서 어려운 점은 이 결정을 후일 번복할 수 없다는 것입니다. 이런 환경에서 작업이 모두 도착했을 때 최대한 많은 작업을 처리하는 것이 목표입니다. 이는 유명한 ..

• 

  Facility location 설비 입지 선정 원-쌍대 근사 알고리즘 (Primal-Dual Approximation Algorithm for Facility Location) 지난 포스트에서 우리는 설비 후보지들이 주어질 때 최소의 비용으로 몇 곳의 후보지에 설비를 지어 모든 고객을 서비스하는 방법을 찾는 설비 입지 선정 문제(facility location problem)를 공부하였습니다. 언뜻 보기에도 산업적으로 유용해 보이는 이 문제는 이론적으로도 흥미로운 부분이 많아서 널리 연구가 되었습니다. 지난 포스트에서는 그중에서도 특히 이 문제를 해결하는 4-근사 알고리즘을 배웠습니다. 설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설 gazelle-and-cs.tistory..