동적 일관적 서브모듈러 최대화 (Dynamic Consistent Submodular Maximization)를 위한 일반 프레임워크

일관성 (Consistency)은 동적 서브모듈러 최대화 (Dynamic Submodular Maximization)에서 중요한 속성으로, 매 단계에서 솔루션에 아주 적은 수의 조정만을 가하면서 항상 최적에 가까운 솔루션을 유지하는 것을 의미합니다. 이전 연구들은 알고리즘이 $n$개의 삽입 스트림을 마주하는 삽입 전용 (insertion-only) 사례에 대해 이 문제를 탐구해 왔으며, 기수 제약 (cardinality-constrained) 버전 문제에 대한 하한 및 상한을 확립했습니다. 본 연구에서는 연산 스트림에 삽입과 삭제가 모두 포함될 수 있는 완전 동적 (fully dynamic) 환경에서 이 문제를 고려합니다. 우리는 이 환경을 위한 알고리즘을 설계하기 위한 일반적인 프레임워크를 개발하며, 이를 구체화하여 준선형 일관성 (sublinear consistency)을 가진 최초의 상수 인자 근사 (constant-factor approximations)를 얻습니다. 기수 제약 (cardinality constraints)의 경우, 우리는 $Oig(rac{1}{\varepsilon^2}\big)$ 일관성을 갖는 $\frac{1}{2} - O(\varepsilon)$ 근사 알고리즘을 제안합니다. 계수-$k$ 매트로이드 제약 (rank-$k$ matroid constraints)의 경우, 동적 최적해 (dynamic optimum)에 대해 $Oig(\frac{\log k}{\varepsilon^2}\big)$ 일관성을 갖는 $\frac{1}{4} - O(\varepsilon)$ 근사 알고리즘을 구축합니다.