근사 알고리즘

컴퓨터 과학 및 운영 연구에서 근사 알고리즘은 최적화 문제(특히 NP-하드 문제)에 대한 대략적인 해결책을 찾아내고,^[1] 반환된 솔루션에서 최적의 솔루션까지의 거리에 대한 입증 가능한 보증을 제공하는 효율적인 알고리즘입니다.근사 알고리즘은 널리 믿어지는 P conject NP 추측의 결과로 이론 컴퓨터 공학 분야에서 자연스럽게 발생한다.이 추측에 따르면, 다양한 종류의 최적화 문제를 정확히 다항식 시간에 해결할 수 없다.따라서 근사 알고리즘 분야는 다항식 시간에 그러한 문제에 대한 최적의 해법을 근사하는 것이 얼마나 가까운지 이해하려고 한다.압도적으로 많은 경우, 이러한 알고리즘의 보증은 근사비 또는 근사계수로 표현되는 승수이다. 즉, 최적의 솔루션이 항상 반환되는 솔루션의 (사전 설정된) 승수 내에 있음을 보증한다.그러나 반환되는 솔루션의 품질에 대한 추가 보증을 제공하는 근사 알고리즘도 많이 있습니다.둘 다 제공하는 근사 알고리즘의 주목할 만한 예로는 관련 없는 병렬 머신에서의 스케줄링을 위한 Lenstra, Shmoys 및 Tardos의^[2] 고전적인 근사 알고리즘이 있습니다.

근사 알고리즘의 설계와 분석은 최악의 ^[1]경우 반환된 솔루션의 품질을 증명하는 수학적 증거를 수반한다.이는 일부 입력에 대해 상당히 좋은 해결책을 찾지만, 초기에 언제 성공할지 또는 실패할지에 대한 명확한 징후를 제공하지 않는 아닐링이나 유전 알고리즘과 같은 휴리스틱스와 구별된다.

특정 유명한 최적화 문제에 근접할 수 있는 한계를 더 잘 이해하기 위해 이론 컴퓨터 과학에 대한 관심이 널리 퍼져 있습니다.예를 들어, 컴퓨터 과학에서 오랫동안 열린 질문 중 하나는 측정기준 순회 판매원 문제에 대한 크리스토피데스의 1.5 근사 알고리즘을 능가하는 알고리즘이 있는지 확인하는 것입니다.근사성의 관점에서 하드 최적화 문제를 이해하고자 하는 욕구는 하드 최적화 문제에 대한 알고리즘을 설계하기 위한 놀라운 수학적 연결과 광범위하게 적용할 수 있는 기술의 발견에 의해 동기 부여된다.전자의 잘 알려진 예로는 최대 컷을 위한 Goemans-Williamson 알고리즘이 있습니다.이 알고리즘은 ^[3]고차원 기하학을 사용하여 그래프 이론상의 문제를 해결합니다.

서론

근사 알고리즘의 간단한 예는 최소 정점 커버 문제에 대한 것입니다. 여기서 목표는 입력 그래프의 모든 가장자리가 적어도 하나의 선택된 정점을 포함하도록 가장 작은 정점 집합을 선택하는 것입니다.정점 덮개를 찾는 한 가지 방법은 다음 프로세스를 반복하는 것입니다. 언노브된 모서리를 찾아서 양쪽 끝점을 커버에 추가하고 그래프에서 두 정점에 포함된 모든 모서리를 제거하는 것입니다.입력 그래프의 정점 커버는 프로세스에서 고려된 각 모서리를 커버하기 위해 서로 다른 정점을 사용해야 하므로(일치를 형성하므로), 생성된 정점 커버는 최적인 것보다 최대 두 배 더 커집니다.즉, 이것은 근사 계수가 2인 상수 요인 근사 알고리즘입니다.최근의 독특한 게임 추정에 따르면, 이 요소는 가능한 최고의 ^[4]요소이다.

NP하드 문제 크게 그들의 approximability에, 일부는 배낭 문제 등 복합적 요소 1+ϵ{1+\epsilon\displaystyle}안에 고정된 ϵ 을, 0{\displaystyle \epsilon>0}이고 따라서 임의로 가까운 근사 algo의 최적(이런 패밀리에 대한 솔루션을 생산할 수 있게 다릅니다.rithms다항식 시간 근사 체계 또는 PTAS)라고 합니다.최대 집단 문제의 경우처럼 P = NP가 아니면 상수 또는 다항식 요인 내에서 근사하는 것이 불가능한 경우도 있습니다.따라서 근사 알고리즘 연구의 중요한 이점은 NP-완전성 이론이 제공하는 문제를 넘어 다양한 NP-하드 문제의 난이도를 세분화하는 것이다.즉, NP-완전 문제는 정확한 해법의 관점에서 (다항식 시간 단축 하에서) 서로 동등할 수 있지만, 대응하는 최적화 문제는 근사 해법의 관점에서 매우 다르게 행동한다.

알고리즘 설계 기술

지금까지 근사 알고리즘을 설계하기 위한 몇 가지 확립된 기술이 있다.여기에는 다음과 같은 것이 포함됩니다.

1. 탐욕 알고리즘
2. 로컬 검색
3. 열거 및 동적 프로그래밍
4. 볼록한 프로그래밍의 완화를 풀고 부분 해법을 얻는다.그런 다음 적절한 반올림을 통해 이 부분 솔루션을 실현 가능한 솔루션으로 변환합니다.인기 있는 릴렉스에는 다음과 같은 것이 있습니다.
   • 선형 프로그래밍의 완화
   • 반무한 프로그래밍 완화
5. 프라이머리 이중 방식
6. 듀얼 피팅
7. 일부 메트릭에 문제를 삽입하고 메트릭에 따라 문제를 해결합니다.이것은 메트릭 임베딩이라고도 합니다.
8. 무작위 샘플링 및 위의 방법과 함께 일반적으로 무작위성 사용.

후자는 보장한다.

근사 알고리즘은 항상 사전 최악의 경우 보증(가산 또는 곱셈)을 제공하지만, 경우에 따라서는 훨씬 더 나은 사후 보증도 제공한다.이것은 종종 주어진 입력에서 최적화 문제의 볼록한 완화를 해결함으로써 작동하는 알고리즘의 경우이다.예를 들어, 최소 정점 커버에 대한 다른 근사 알고리즘이 있어 완화 값의 최대 두 배인 정점 커버를 찾기 위해 선형 프로그래밍 이완을 해결합니다.완화의 값이 최적 정점 커버의 크기보다 결코 크지 않기 때문에 다른 2-근사 알고리즘이 생성됩니다.이것은 이전 근사 알고리즘의 선행 보증과 비슷하지만 후자의 보증은 훨씬 더 좋을 수 있습니다(실제로 LP 완화 값이 최적 정점 커버의 크기와는 거리가 먼 경우).

근사의 경도

연구 영역으로서의 근사 알고리즘은 특정 근사 비율을 가진 효율적인 알고리즘의 부존재가 감소를 통해 증명되는(P np NP 추측과 같이 널리 믿어지는 가설에 따라 조건화됨) 부존재성 이론과 밀접하게 관련지어지고 있다.미터법 이동 판매원 문제의 경우, P = NP, Karpinski, Lampis, ^[5]Schmied가 아닌 한, 가장 잘 알려진 비근사성 결과는 123/196 6 1.008196 미만의 알고리즘을 제외합니다.Christofides의 1.5 근사 알고리즘의 존재에 대한 지식과 함께, 이것은 미터법 여행 세일즈맨의 근사성의 역치가 123/122와 1.5 사이라는 것을 알려준다.

1970년대 이후 비직접성 결과가 입증되었지만, 그러한 결과는 임시방편으로 얻어진 것이며 당시에는 체계적인 이해가 없었다.1990년 Feige, Goldwasser, Lovasz, Safra 및 Szegedy가 Independent^[6] Set의 비직접성과 유명한 PCP ^[7]정리에 대해 실시한 결과에서야 비직접성 결과를 입증하는 최신 도구가 발견되었다.예를 들어 PCP 정리는 Johnson의 1974년 Max SAT, 세트 커버, 독립 세트 및 컬러링에 대한 근사 알고리즘이 P np ^[8]NP라고 가정할 때 모두 최적의 근사비를 달성함을 보여준다.

실용성

모든 근사 알고리즘이 직접 실제 적용에 적합한 것은 아닙니다.일부는 비사소한 선형 프로그래밍/반무한 완화(타원체 알고리즘을 호출할 수도 있음), 복잡한 데이터 구조 또는 정교한 알고리즘 기술을 해결하는 것을 포함하며, 이는 실행 문제가 어렵거나 실행 시간 성능이 (정확한 알고리즘보다) 비현실적으로 큰 입력에서만 향상됩니다.구현 및 실행 시간 문제는 차치하고 근사 알고리즘에 의해 제공되는 보증 자체가 실제 고려 사항을 정당화할 만큼 충분히 강력하지 않을 수 있다.이러한 알고리즘은 실제 적용에서 "즉시" 사용할 수 없음에도 불구하고, 그러한 알고리즘의 설계 뒤에 있는 아이디어와 통찰력은 종종 실제 알고리즘에 다른 방식으로 통합될 수 있습니다.이와 같이 매우 비싼 알고리즘에 대한 연구도 귀중한 통찰력을 얻을 수 있기 때문에 완전히 이론적인 추구는 아닙니다.

다른 경우에는 초기 결과가 순수하게 이론적인 관심사일지라도 시간이 지남에 따라 이해가 향상되어 알고리즘이 보다 실용적이 되도록 개선될 수 있다.그러한 예로는 Sanjeev Arora(및 Joseph Mitchell에 의해 독립적으로)에 의한 유클리드 TSP의 초기 PTAS가 있습니다.이 PTAS는 1${\displaystyle }$+$$ \ $displaystyle$ 1 + \ $epsilon }$^[9]의 근사치에 ${\displaystyle {대해}^{}}$n${\displaystyle {\mathrm{O}}^{}}$( ${\displaystyle 1^{}}$ / $)$ ) {$O$ ( $1$/ ) ) }의 엄청난 실행 시간을 가지고 있었습니다.단, 1년 이내에 이러한 아이디어는 의 상수 $>$ 0$(\displaystyle \epsilon >$ 0^[10]에 대해 선형에 $가까운{\displaystyle }$ 시간$(n log$ n$)$ 알고리즘에 통합되었습니다.

퍼포먼스 보증

일부 근사 알고리즘에서는 최적 결과의 근사치에 대한 특정 특성을 증명할 수 있다.예를 들어 δ근사 알고리즘 A는 인스턴스 x에 대한 근사해 A(x)의 값/비용 f(x)가 최적해 값 OPT를 곱한 계수 δ보다 크지 않음을 증명한 알고리즘으로 정의한다.

${\displaystyle {begin{case}\mathrm {OPT}\leq f(x)\leq \mathrm {OPT},\qqquad {mbox},\rho >1;\rho \mathrm {OPT},\leq \mathrm {OPT} {OPT},\rm {opt},\rm},\rm {opt},\rm {opt},\rm},\rm {opt}, {opt},\r\end {case}}$

계수 is는 상대적 성능 보증이라고 불립니다.근사 알고리즘은 모든 인스턴스 x에 대해 증명된 경우 절대 성능 보증 또는 경계 오류 c를 가집니다.

$\displaystyle(\mathrm {OPT} -c)\leq f(x)\leq(\mathrm {OPT} +c).}$

마찬가지로 인스턴스 x에 대한 솔루션 y의 성능 보증 R(x,y)는 다음과 같이 정의됩니다.

${\displaystyle R(x,y)=\max \leftfac {OPT}{f(y)}, {\frac {f(y)}{OPT}}\right},}$

여기서 f(y)는 인스턴스 x에 대한 솔루션 y의 값/비용입니다. 분명히 성능 보증은 y가 최적의 솔루션인 경우에만 1 이상이고 1과 같습니다.알고리즘 A가 최대 r(n)의 성능 보증으로 해답을 반환하는 것을 보증하는 경우, A는 r(n)-근사 알고리즘이며 r(n)의 근사 비율을 가진다.마찬가지로 r(n)-근사 알고리즘의 문제는 r(n)-근사 가능하거나 r(n)^[11][12]의 근사비를 갖는다고 한다.

최소화 문제의 경우, 두 가지 다른 보증은 동일한 결과를 제공하며, 최대화 문제의 경우 δ의 상대적 성능 보증은 r $=$ - 1$(\$ r=\$rho$^{-$1$의 성능 보증과 동등하다. 문헌에서는 두 정의가 공통적이지만 m에 대해 사용된 정의는 명확하다.aximization 문제('1'과 r'1 등).

일부 근사 알고리즘A의 절대 성능 $보증{\displaystyle {\mathrm{}}_{}}$ P $($x는 문제의 인스턴스를 나타내며 $x)$는 x(즉, 문제 x)에 대한 A의 성능 보증이다)의 절대 보증 P A(\$displaystyle$ $\mathrm {P}_$${A}(x))$는 다음과 같습니다.

$\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}$

즉, $(\$${A})$는 문제의 모든 가능한 예에서 볼 수 있는 근사 비율 r의 최대 경계입니다.마찬가지로 점근 $성능비{\displaystyle {}_{}^{}}$ ${\displaystyle R_{}^{}}$ A ${\$ {\$displaystyle R_{A}^{\infty$}}는$$ 다음과 같습니다.

${\displaystyle R_{A}^{\infty}=\inf\{r\geq 1\mid \mathbb {Z}^{+},R_{A}(x)\leq r,\forall x,x \geq n\}.}$

즉, 절대 퍼포먼스 비율과 동일하며 문제 인스턴스의 크기에는 하한n이 있습니다.이들 2종류의 비율이 사용되는 이유는 이들 2종류의 차이가 큰 알고리즘이 존재하기 때문입니다.

퍼포먼스 보증

	대략[11][12]	약 킬로	관련 오류[12]	관련 오류[11]	norm. rel. 오류[11][12]	abs. 오류[11][12]
max:${\displaystyle }f{\displaystyle }$ (${\displaystyle x}$ ) ${\$ { $display style f ($ x )\ $geq }$	${\displaystyle r^{-1}\mathrm {OPT}}$	${\displaystyle \rho \mathrm {OPT}}$	${\displaystyle (1-c)\mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} +c\mathrm {WORST} }$	$\displaystyle \mathrm {OPT} -c}$
min:${\displaystyle }f{\displaystyle }$ (${\displaystyle x}$ ) ${\$ { $display style$f ($x$ )\$leq }$	${\displaystyle r\mathrm{오피티}}$	${\displaystyle \rho \mathrm {OPT}}$	${\displaystyle(1+c)\mathrm{오피티}}$	${\displaystyle(1-c)^{)}\mathrm{오피티}}$	${\displaystyle(1-c)^{)}\mathrm{오피티}+c\mathrm{WORST}}.$	${\displaystyle \mathrm{오피티}+c}$

엡실론 항

문헌에서, 댁-ϵ(min:댁+ϵ)의 극대화(극소화)문제에 대한 근사 비율은 알고리즘 임의의 ϵ 을에 c∓ ϵ에 대한 근사치 비율이;0이지만 비율이 ϵ=0로 방영될(또는 수 있지 않)지 않았다. 근사 7/8의 비율 — 이것의 예는 최적의 inapproximability — inexistence을 의미한다. +ϵ만족시킬 수 있는 MAX-3SAT 인스턴스의 경우 요한 Håstad에 따른 것이다.[13]때 c=1, 문제는 다차 함수 시간 근사 계획이 있다고 한다 이전에 언급된 것.

로 n 있는 반면, 크기 n의 인스턴스의 최소 최적점 무한으로 갈 때 근사치 알고리즘은 곱셈의 오류와 일정한 오류를 소개하고 있는 ϵ-term 나타날 수 있다.이 경우에, 근사 비율은 c∓ k/오피티 몇몇 상수 c에∓ o(1)c=과 k임의의 ϵ>0을 감안할 때, 충분히 큰 N을 선택할 수 있는은 용어 k/오피티<>ϵ를 위해 n≥ N을 위해 매일 고정 ϵ 인스턴스의 크기 n<>N이 될 수 있게 해 주기에 의해 폭력,을 보여 주는 근사 비율— 존재의 근사 알고리즘으로 보증 —의 c∓ ϵ를 위해 ϵ>0.

「 」를 참조해 주세요.

• 통일 천하 분석은computed 해결책의 지위 면에서 보증을 고려하고 있다.
• PTAS-근사 알고리즘 매개 변수로 근사 비율이 걸리는 형식입니다.
• 일부constant-factor 근사 알고리즘의 문제와 관련된 APC는 클래스입니다.
• 감소 Approximation-preserving
• 정확한 알고리즘

인용문

이 글이지만 충분한 해당하는 인라인 인용이 부족한 일반적인 참고 문헌 목록이 포함되어 있다. 좀 더 정확한 인용문을 도입하여 이 기사의 개선에 협조해 주십시오.(2009년 4월) (이 템플릿메시지의 삭제 방법 및 삭제 타이밍에 대해 알아보기)

레퍼런스

• Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 978-3-540-65367-7.
• 토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제2판MIT Press and McGraw-Hill, 2001.ISBN 0-262-03293-7.35장: 근사 알고리즘, 페이지 1022–1056.
• 도릿 S. 호치바움, EDNP-Hard 문제에 대한 근사 알고리즘, PWS Publishing Company, 1997.ISBN 0-534-94968-1.9장: 근사치의 다양한 개념: 양호, 양호, 최적 및 기타
• Williamson, David P.; Shmoys, David B. (April 26, 2011), The Design of Approximation Algorithms, Cambridge University Press, ISBN 978-0521195270

외부 링크

• Pierluigi Crescenzi, Viggo Kann, Magnus Haldorsson, Marrek Karpinski 및 Gerhard Woeginger, NP 최적화 문제의 개요.