맥스 나는 그래프 <code>G = (V,E)</code>을 제공하고있어이 문제에 알고리즘

Question

3 색, 목표는

Q (C) 품질 기능을 극대화 할 수 3 색으로 그래프의 정점의 색을 찾을 수 있습니다의 수를 = 끝점의 색상이 다르게 표시되는 가장자리.

는 probalistic 3/2 근사치를주고, 알고리즘 수익률은 각각 자연수 k과 고정 d>= 1 대부분의 d^-k에서 확률 (더 근사치를 의미) 실패 것으로 나타났다.

이제 다음과 같은 알고리즘을 제공합니다. 각 꼭지점을 임의로 색상 지정합니다. 즉, 가장자리가 다른 색상 가장자리를 가질 것으로 예상되는 확률이 3/2 근사치 인 2/3입니다.

그래도 나는 그것이 최대로 d^-k의 확률로 실패를 반환하는 방법을 알 수 없습니다.

도움을 주셔서 감사합니다.

Answer 1

여기서 한정 기호를 풀지 않고 다음과 같이 결정적으로 구현 가능한 욕심 많은 알고리즘을 올바른 것으로 증명하기 위해 조건부 기대치 방법을 사용할 수 있습니다.

색상이없는 꼭지점이 있지만 그 중 가장 가까운 색상으로 색상을 지정하십시오.

다른 채색을 무작위로 채색한다고 가정 할 때, 채색되지 않은 종점을 가진 각 모서리는 다른 선택이 무엇이든 관계없이 예상치로 2/3의 가치가 있다고 생각합니다. 가장 다양한 선택을 사용함으로써, 우리는 무작위 가치로 잃어버린 것보다 적어도 결정 론적 가치를 얻습니다.