슈타이너 트리의 양방향 컷 완화 정수성 간극
슈타이너 트리 문제는 네트워크 설계 분야의 핵심 난제 중 하나입니다. 이 문제는 주어진 가중치 그래프에서 특정 터미널 노드들을 모두 포함하는 최소 가중치 트리를 찾는 것을 목표로 합니다. 현재 알려진 최적 근사 알고리즘들은 많은 수의 후보 구성 요소를 열거해야 하므로 실제 적용에는 속도 제약이 있습니다. 이러한 한계를 극복하기 위해 양방향 컷 완화(BCR)가 유망한 대안으로 주목받고 있습니다. BCR은 모든 엣지를 양방향화하고 임의의 터미널을 루트로 설정한 뒤, 루트를 포함하지 않는 모든 컷에 대해 분수 엣지 흐름이 1단위가 되도록 강제하는 방식입니다. 모든 정점이 터미널인 신장 트리 문제의 경우 BCR은 정수성을 보장함이 알려져 있습니다. 그러나 일반적인 슈타이너 트리 인스턴스에서는 BCR의 정수성 간극이 기존의 비방향 컷 완화의 정수성 간극(정확히 2)보다 나은지조차 불분명했습니다. 본 연구는 이 질문에 대한 해답을 제시합니다. 우리는 BCR의 정수성 간극이 1.9988보다 작음을 수학적으로 증명했습니다. 이 결과는 슈타이너 트리 문제 해결을 위한 빠르고 정확한 근사 알고리즘 설계에 중요한 이론적 기반을 제공하며, 네트워크 최적화 분야의 발전에 기여할 것입니다.