본 논문은 다수의 서브모듈러 제약 조건을 다루는 문제를 고려합니다. 유한 집합 N, 비용 함수 c: N → ℝ+, N 상의 r개의 단조 서브모듈러 함수 f₁, f₂, ..., fᵣ 및 요구 사항 b₁, b₂, ..., bᵣ이 주어지면, 모든 1 ≤ i ≤ r에 대해 fᵢ(S) ≥ bᵢ인 최소 비용 부분 집합 S ⊆ N을 찾는 것이 목표입니다. r=1인 경우, 이는 잘 알려진 서브모듈러 집합 덮개 문제입니다. 기존 연구는 r이 클 때 이중 기준 근사 알고리즘과 각 fᵢ가 가중치 덮개 함수인 중요한 특수한 경우에 대한 근사 알고리즘을 개발했습니다. 이들은 상당히 일반적인 모델이며 여러 구체적이고 흥미로운 문제를 특수한 경우로 포착합니다. 이 문제에 대한 근사 비율은 적어도 Ω(log r)이며, r이 입력의 일부인 경우 불가피합니다. 본 논문에서는 최근 몇몇 응용 프로그램에 착안하여 r이 고정 상수인 경우를 고려하고 두 가지 주요 결과를 얻습니다. 다수의 서브모듈러 제약 조건을 덮는 경우, 주어진 정수 α ≥ 1에 대해 각 i ∈ [r]에 대해 fᵢ(S) ≥ (1-1/e^α -ε)bᵢ이고 E[c(S)] ≤ (1+ε)α · OPT인 집합 S를 출력하는 랜덤 이중 기준 근사 알고리즘을 얻습니다. 두 번째로, fᵢ가 삭제-폐쇄 집합 시스템의 가중치 덮개 함수인 경우, 기본 집합 덮개 인스턴스에 대한 자연적인 LP를 통한 근사 비율이 β인 (1+ε)(e/(e-1))(1+β)-근사를 얻습니다. 이러한 결과는 고정된 r에 대해 r=1일 때 달성할 수 있는 것과 거의 동일한 근사를 얻을 수 있음을 보여줍니다. 본 논문에서는 이러한 일반적인 결과에서 쉽게 도출되는 몇 가지 응용 프로그램을 언급하고 향후 더 많은 응용 프로그램을 예상합니다.
