근사의 경도

컴퓨터 과학에서, 근사 경도는 최적화 문제에 대한 거의 최적의 해결책을 찾는 알고리즘의 복잡성을 연구하는 분야이다.

범위

근사 경도는 특정 문제에 대해 솔루션을 효율적으로 근사할 수 있는 인자의 한계를 증명함으로써 근사 알고리즘의 연구를 보완한다.일반적으로 이러한 한계는 문제가 NP-hard가 되는 근사 계수를 나타내며, 이는 NP=P가 아닌 한 문제에 대한 다항식 시간 근사치를 찾는 것이 불가능하다는 것을 의미한다.그러나 근사 결과의 일부 경도는 다른 가설에 기초하며, 그 중 주목할 만한 것은 독특한 게임 추측이다.

역사

1970년대 초반부터 P = NP가 아니면 많은 최적화 문제를 다항 시간에 해결할 수 없다고 알려져 있었지만, 이러한 문제들 중 많은 경우 최적 해법은 어느 정도 효율적으로 근사할 수 있었다.1970년대, Teofilo F. Gonzalez와 Sartaj Sahni는 특정 최적화 문제가 주어진 근사 비율 내에서조차 NP-hard라는 것을 보여줌으로써 근사 경도의 연구를 시작했다.즉, 이러한 문제의 경우, 이 임계값을 초과하는 근사 비율을 가진 모든 다항 시간 근사치가 다항 ^[1]시간에서의 NP-완전 문제를 해결하기 위해 사용될 수 있는 임계값이 있습니다.1990년대 초, PCP 이론의 발전과 함께, 더 많은 근사 문제들은 근사하기가 어려웠고, (P = NP가 아닌 한) 많은 알려진 근사 알고리즘이 가능한 최선의 근사 비율을 달성했다는 것이 분명해졌다.

근사 이론의 경도는 그러한 문제의 근사 역치를 연구하는 것을 다룬다.

예

근사하기 어려운 NP-하드 최적화 문제의 예는 set cover를 참조하십시오.

「 」를 참조해 주세요.

• PCP 정리

레퍼런스

추가 정보

• Trevisan, Luca (July 27, 2004), Inapproximability of Combinatorial Optimization Problems (PDF)

외부 링크

• CSE 533: 근사치의 PCP 정리와 경도, 2005년 가을, 워싱턴 대학교 벤카테산 구루스와미, 라이언 오도넬의 강의요강