metric (3) 썸네일형 리스트형 거리의 트리 실현 가능성 (Tree Realizability of Distance) 오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로 포스팅을 할 생각도 있었는지라 블로그에 글을 쓰는 것이 늦어졌습니다. 색다른 주제는 바로 양자 컴퓨팅(quantum computing)입니다. 하도 화제인지라 개인적으로도 공부해 보고 싶었습니다. 처음에는 전혀 이해가 되지 않았는데 이 책 저 책 찾아보면서 공부하다 보니 이제는 좀 이해가 되는군요. 언젠가 해당 주제로 포스팅을 해 보도록 하겠습니다. 각설하고, 이번 글의 주제를 고민하게된 배경에 대해서 간략히 설명을 드리겠습니다. 요새 온라인 메트릭 매칭 문제(online metric matching problem)를 (제가 찾아본 바로는) 기존에는 없던 새로운 모델에서 해결해 보는 연구를 진행하고 있습니다. 그런데 일반적인 메.. 온라인 메트릭 이분 매칭 (Online Metric Bipartite Matching) 지난 포스트에서는 온라인 가중치 이분 매칭(online weighted bipartite matching)에 대해서 알아 보았습니다. 이 문제에서는 택시에 대한 정보는 미리 알고 있으며, 승객의 정보는 시간이 흐르면서 한 명씩 들어옵니다. 매 순간 어떤 승객의 정보가 알려질 때마다 우리는 이 승객을 택시에 할당할지 말지를 결정해야 하며, 만약 할당한다면 어느 택시에 태울지도 결정해야 합니다. 지난 포스트에서는 언젠가 승객을 어떤 택시에 할당했을 때 이를 더이상 번복할 수 없다면 좋은 경쟁비(competitive ratio)를 얻을 수 없다는 것을 확인하였습니다. 자세한 사항은 이전 포스트를 참고하시기 바랍니다. 2021.02.14 - [온라인 알고리즘/Online matching] - 온라인 가중치 이분.. [외판원 문제 / TSP] 메트릭 & 2-근사 (Metricity & 2-Approximation) 안녕하세요. 이번에는 traveling salesman problem에 대해서 알아보도록 하겠습니다. 주로 줄여서 TSP라고도 부르며, 제가 알기로 우리말로는 외판원 문제로 불립니다. 개괄적인 설명은 이전 글에서 했습니다. 2019/07/10 - [근사 알고리즘] - 근사 알고리즘 근사 알고리즘 (Approximation Algorithm) 현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요? 아.. gazelle-and-cs.tistory.com 그러니 이번에는 서두 없이 바로 문제를 정의해 보도록 하겠습니다. 문제의 입력으로 지점들의 집합 V와 .. 이전 1 다음
