카를로프-즈윅 알고리즘

Karloff–Zwick algorithm

Karloff-Zwick 알고리즘은 계산 복잡성 이론에서 MAX-3SAT Boolean 만족도 문제의 예를 입력으로 하는 랜덤화된 근사 알고리즘이다.인스턴스가 만족스러운 경우 발견된 임무의 예상 중량은 최소 최적치의 7/8이다.알고리즘이 만족스럽지 못한 MAX-3SAT 인스턴스에서도 최적의 7/8을 달성한다는 강력한 증거가 있다(수학적 증거는 아님).하워드 카를로프와 우리 즈윅은 1997년에 이 알고리즘을 제시했다.[1]

알고리즘은 예를 들어, 동일한 근사 보증을 가진 결정론적 다항식 시간 알고리즘을 산출하는 기법을 사용하여 비논리화할 수 있다.

무작위 할당과 비교

입력 3SAT 공식의 모든 조항이 정확히 3리터를 갖도록 보장되는 관련 MAX-E3SAT 문제의 경우, 각 변수에 독립적이고 균일하게 임의로 진실 값을 할당하는 단순 랜덤화 근사 알고리즘은 원래 공식의 존재 여부에 관계 없이 기대되는 모든 조항의 7/8을 만족한다.만족스러운또한, 이 간단한 알고리즘은 조건부 기대의 방법을 사용하여 쉽게 디앤더링할 수 있다.그러나 카를로프-즈윅 알고리즘은 입력 공식에 모든 조항에서 3 리터럴이 있어야 한다는 제한을 요구하지 않는다.[1]

최적성

PCP 정리에 관한 이전 연구를 바탕으로, Johan Håstad는 P each NP를 가정했을 때, 각 조항이 정확히 3리터를 포함하는 문제의 만족스러운 사례로 제한된 경우에도 MAX 3SAT에 대한 어떤 다항 시간 알고리즘도 7/8을 초과하는 성능 비율을 달성할 수 없다는 것을 보여주었다.따라서 카를로프-즈윅 알고리즘과 위의 간단한 알고리즘 모두 이러한 의미에서 최적이다.[3]

참조

  1. ^ a b Karloff, H.; Zwick, U. (1997), "A 7/8-approximation algorithm for MAX 3SAT?", Proceedings 38th Annual Symposium on Foundations of Computer Science, pp. 406–415, CiteSeerX 10.1.1.51.1351, doi:10.1109/SFCS.1997.646129, ISBN 978-0-8186-8197-4.
  2. ^ Sivakumar, D. (19 May 2002), "Algorithmic derandomization via complexity theory", Proceedings of the thiry-fourth annual ACM symposium on Theory of computing: 619–626, doi:10.1145/509907.509996
  3. ^ Hastad, J. (2001), "Some optimal inapproximability results", Journal of the ACM, 48 (4): 798–859, CiteSeerX 10.1.1.638.2808, doi:10.1145/502090.502098.