무작위 결정 네트워크에서의 상관관계 감소

우리는 각 노드가 결정 변수를 나타내는 비방향 그래프에서 결정 네트워크를 고려하며, 그래프의 각 노드와 엣지는 해당 노드의 변수에만 의존하는 보상 함수와 연관되어 있습니다. 목표는 총 보상을 극대화하는 결정 벡터를 구성하는 것입니다. 이 결정 문제는 그래픽 모델에서의 최대 우도 추론(마르코프 랜덤 필드), 그래프에서의 조합 최적화, 경제 팀 이론 및 통계 물리학을 포함한 다양한 모델을 포함합니다. 네트워크는 보상이 분포에서 샘플링되는 확률적 구조를 부여받습니다. 우리의 목표는 네트워크 구조와 보상 분포에 대한 충분한 조건을 식별하여 기본 최적화 문제의 평균-case 다항성을 보장하는 것입니다. 또한, 우리는 지역 정보를 기반으로 생성된 분산된 솔루션의 효율성을 특성화하고자 합니다. 우리는 'Cavity Expansion'이라는 새로운 분산 알고리즘을 구성하고, 다양한 그래프 모델과 보상 함수 분포에 대한 이론적 성능을 설정합니다. 특히, 특정 모델 클래스에 대해 우리의 알고리즘이 높은 확률로 분산 방식으로 근사 최적 솔루션을 찾을 수 있음을 증명합니다. 알고리즘의 성공은 네트워크가 특정 상관관계 감소(장기 독립성) 특성을 나타내는 것에 근거하며, 우리는 관심 있는 모델에서 이 특성이 실제로 나타난다는 것을 증명합니다. 우리의 결과는 알고리즘의 평균-case 복잡성 영역에서 다음과 같은 놀라운 함의를 가집니다. 그래프의 최대 독립 집합(안정 집합)을 찾는 것은 잘 알려진 NP-난해 최적화 문제로, 최대 연결성이 3인 그래프에 대해서는 P = NP가 아닌 한 다항 시간 근사_scheme가 불가능합니다. 그러나 우리는 같은 클래스의 그래프에 대한 밀접한 관련 Maximum Weight Independent Set 문제가 보상이 독립적이고 동일하게 분포되는 경우 PTAS를 허용함을 보여줍니다. 즉, 보상 함수의 무작위화가 NP-난해 문제를 처리 가능한 문제로 변환합니다.