생각의 전환 – Strong Duality

듀얼리티… 개념이 정말 안 잡혀서 고생이다. 단어 뜻으로 풀어보면 이중성이라는 뜻인데…문제의 이중성을 얘기한다. 가령 어떤 난해한 문제를 고심해도 풀지 못할 때, 의외로 다른 방향으로 생각하면 쉽게 풀..

어떤 문제가 안풀릴 때, 다른 관점으로 보면 쉽게 풀리는 경우가 있다. 그리고 그 방법만 만족되면 원래의 문제는 더이상 고려 안해도 되는 강한 경우를 Strong Duality라고 한다.

Strong Duality 문제의 예로 그래프상에서 모든 간선을 커버하는 정점을 찾는 Vertex CoverSet 찾기 문제와 그와 Duality인 Matching 문제를 든다. 즉, 모든 간선을 커버하는 최소개의 정점을 찾는 문제는 어렵지만, 매칭문제로 간선을 찾아 중복되지 않는 정점을 선택하는 것은 상대적으로 매우 쉬운 문제가 된다.

이와 같은 생각의 전환은 Optimal Solution을 찾고자 할 때 적용하면 효과가 크다. 고정된 액수의 광고비를 가지고 최대의 효과를 올릴 수 있는 광고 아이템을 선정하고자 할 때 어떻하면 될까? 리니어 프로그래밍으로 여러 x개의 변수를 넣고 최적화를 풀지 말고, Duality로서 x 변수들의 결과값의 lower bound를 선정하고 그에 해당하는 x 변수들의 범위를 그려 선정하면 비교적 쉬운 문제가 된다.

정말 문제는, 이런 내용을 풀어서 써 놓은 한글 문서가 없다는 거다. -_-;