FOCS2018 (알고리즘 탑 컨퍼런스중 하나)랑 Duke에 실린 아래 논문에서는 허준이교수님의 결과를 이용하여 매트로이드의 base 갯수를 approximate하는 다항시간 알고리즘을 제시함
https://arxiv.org/abs/1807.00929 Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids
이런 연구는 이후에 base를 잘 뽑는 random process를 디자인 하는 데에 활용될 수 있고 매트로이드는 굉장히 다양한 대상을 아우르기 때문에 이것은 여기저기에 사용될 수 있음.
예를 들어 연결 그래프에서는 base가 spanning tree인데 random spanning tree가 어떤 edge를 포함하는 확률을 계산하는 문제는 그래프의 effective resistance를 계산하는 문제랑 연관되어 있고
그것말고도 여러 최적화문제의 근사해를 구하는 문제랑도 연관이 되어 있음
아무튼 쓸데가 있기는 하다
댓글 0