Teofilo F. Gonzalez (2007), Handbook of Approximation Algorithms and Metaheuristics, Taylor & Francis Group.
노트정리/알고리즘 놀이 2016. 5. 24. 11:21그래프 쪽으로 참고하려고 학교에 주문 신청했으나 결국 논문을 직접 찾아서 공부하였음
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 최적해}$$
'노트정리 > 알고리즘 놀이' 카테고리의 다른 글
| DBSCAN 자바 구현 실습 소스 코드 (4) | 2017.10.17 |
|---|---|
| 바이오인포매틱스 프로그래밍 연습 사이트 (0) | 2017.05.08 |
| 2차원 공간에서 퍼지 클러스터링(fuzzy clustering) 자바 구현 (0) | 2016.06.03 |
| 블로그의 스팸 덧글 검출하는 방법 - 자카드 유사도(Jaccard similarity). 자바 구현. (2) | 2016.06.03 |
| 삽입 정렬(insertion sort) 자바로 구현. (0) | 2015.12.31 |
| Skyline operator 세미나 프리젠테이션 자료 (2) | 2015.08.08 |
| 스카이라인 오퍼레이터 의사코드 Skyline Operator Pseudo code (0) | 2015.07.30 |
| 자바로 구현한 퀵 소트(quick sort), 자바 소스 코드 (2) | 2015.07.09 |
