Min weighted edge cover-탐욕스러운 알고리즘이 차선책입니까?

Nov 27 2020

여기에 게시물 : 최대 일치 알고리즘을 사용하여 최소 가장자리 덮개를 해결하면 모든 정점이 덮일 때까지 최대 일치 위에 가장자리를 탐욕스럽게 추가하여 최대 일치에서 최소 가장자리 덮개를 얻는 방법을 제공합니다. 이제 min-weighted edge cover 문제에 대해 생각하면이 접근 방식을 확장 할 수있는 것처럼 보입니다. 먼저 최대 간선과 일치하는 최소 가중치를 찾은 다음 가장 작은 가중치의 간선을 탐욕스럽게 추가하고 가장 작은 가중치의 간선을 먼저 추가합니다.

그러나 Schrijver의 "조합 최적화 : 다면체 및 효율성"책의 19.3 절을 읽으면 더 복잡한 알고리즘이 제시됩니다. 이것은 위의 접근 방식이 차선책 인 것처럼 보입니다. 탐욕스러운 알고리즘이 최적의 솔루션을 제공하지 못하는 양분 그래프에서 반례를 찾을 수 있습니까? 장난감 그래프가있는 것을 찾지 못했습니다.

답변

1 j_random_hacker Nov 28 2020 at 04:01

다음은 제안 된 알고리즘에 대한 반례입니다.

최적의 솔루션은 3 개의 모서리로 구성되고 비용은 3 + 1 + 1 = 5이지만, 2 개의 모서리로 구성되고 비용이 3 + 3 = 6 인 최소 비용 최대 카디널리티 일치는 알고리즘의 첫 번째 단계에서 선택됩니다. 이미 솔루션이므로 즉시 반환됩니다. (다른 최대 카디널리티 일치 비용은 1 + 6 = 7입니다.)