그래프 쪽으로 참고하려고 학교에 주문 신청했으나 결국 논문을 직접 찾아서 공부하였음


Teofilo F. Gonzalez (2007), Handbook of Approximation Algorithms and Metaheuristics, Taylor & Francis Group.


근사 알고리즘(approximation algorithm)을 증명하는 방법을 정리해둔 책




근사 알고리즘이란, 어떤 알고리즘이 찾아낸 해(solution)가 최적해(optimal solution) 대비 어느 정도 까지 성능이 보장되는가라고 생각하면 될듯


2-approximation algorithm에 관해,


최대값을 찾는 알고리즘의 경우


$$2={최적해 \over 최대값}$$


최소값을 찾는 알고리즘의 경우


$$2 = {최소값 \over 최적해}$$






신고
Posted by 공돌이pooh

댓글을 달아 주세요