단일 패스 반스트리밍 매칭에서 Greedy 알고리즘이 최적임을 증명
Greedy is optimal for single-pass semi-streaming matching
Sepehr Assadi, Max Jiang, Mars Xiang 연구진이 arXiv에 발표한 논문으로, 단일 패스 semi-streaming 알고리즘(결정적 또는 무작위)이 최대 매칭 문제에 대해 1/2보다 나은 근사 비율을 달성할 수 없음을 증명했습니다. 이는 그래프 스트리밍 분야에서 20년 넘게 미해결 상태였던 질문에 답하며, naive greedy 알고리즘의 최적성을 입증합니다. 증명은 저자들이 이전에 도입한 'blueprint' 프레임워크를 따르며, 최적의 blueprint 구성을 제시합니다. 또한 이 결과는 preemption을 허용하는 온라인 매칭의 최적 경쟁 비율이 1/2임을 시사합니다.
우리는 단일 패스 semi-streaming 알고리즘(결정적 또는 무작위)이 최대 매칭 문제에 대해 1/2보다 나은 근사 비율을 달성할 수 없음을 증명하며, 이는 모델 도입 이후 20년 넘게 미해결 상태였던 그래프 스트리밍 문헌의 중요한 공개 질문에 답합니다.