근사 알고리즘 (approximation algorithm)
쉽게 풀면
근사 알고리즘은 '완벽한 정답을 찾는 것은 너무 오래 걸리니, 대신 최적해에서 크게 벗어나지 않는다는 것을 수학적으로 보장할 수 있는 답을 빠르게 구하자'는 전략이다. 예를 들어 어떤 근사 알고리즘이 '항상 최적해의 두 배 이내의 값을 반환한다'는 것을 증명할 수 있다면, 이 알고리즘은 2-근사 알고리즘이라고 불린다. 이는 그냥 아무렇게나 어림짐작하는 휴리스틱과 달리, 최악의 경우에도 얼마나 최적해에서 벗어날 수 있는지에 대한 확실한 수학적 한계를 제공한다는 점이 중요한 차이다.
왜 중요한가
현실의 최적화 문제 상당수는 NP-난해로 분류되어 입력 크기가 커지면 정확한 최적해를 구하는 것이 사실상 불가능하다. 근사 알고리즘은 이런 상황에서 '얼마나 틀릴 수 있는지'를 수학적으로 못박은 채 실용적인 시간 안에 답을 낼 수 있게 해주므로, 이론 컴퓨터과학뿐 아니라 네트워크 설계, 자원 스케줄링, 클러스터링, 운영 연구 등 실무형 최적화 문제를 다루는 논문에서 핵심적으로 다뤄진다. 또한 어떤 문제가 얼마나 잘 근사될 수 있는지, 혹은 근사 자체가 어렵다는 것을 밝히는 것 자체가 계산복잡도 이론의 주요 연구 주제이기도 하다.
논문에서는 이렇게 쓰입니다
NP-난해 문제에 대해 정확해 대신 성능이 보장된 근사해를 구하는 실용적 접근법을 설명할 때 사용된다.
네트워크·시스템 설계 분야에서 조합 최적화 문제를 근사 알고리즘으로 풀어 성능 보장을 얻는 사례를 보여준다.
이론 컴퓨터과학 논문에서 선형·반정값 계획법 완화를 활용해 근사 비율 자체를 개선하는 연구 흐름을 나타낼 때 사용된다.
조금 더 깊게 보면
근사 알고리즘을 다루는 논문에서는 근사 비율(approximation ratio) 외에도 완화(relaxation) 기법이 자주 등장하는데, 정수계획법으로 정의된 문제를 선형계획법이나 반정값 계획법으로 느슨하게 풀고 그 해를 반올림(rounding)하여 실행 가능한 해로 만드는 방식이 대표적이다. 이런 접근이 얼마나 좋은 근사 비율을 낼 수 있는지에는 한계가 있는데, 특정 문제는 어떤 다항 시간 알고리즘으로도 일정 비율 이상 근사하기 어렵다는 것을 보이는 근사 불가능성(inapproximability) 결과도 함께 논의되곤 한다. 또한 근사 비율이 입력 크기에 따라 서서히 나빠지는 알고리즘과, 항상 일정한 상수 비율을 유지하는 알고리즘(상수 근사)은 성능 보장의 강도가 다르므로 논문을 읽을 때 이 구분을 눈여겨볼 필요가 있다.
주의할 점
근사 알고리즘의 근사 비율은 최악의 경우를 기준으로 증명된 것이므로, 실제 데이터에서는 그 한계보다 훨씬 더 좋은 결과를 내는 경우도 많지만 이는 보장된 사실이 아니다.