알고리즘서지만 확인
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingMichel X. Goemans, David P. Williamson · 1995Journal of the ACM 42(6), 1115–1145쪽 (1995) · 학회 발표 STOC 1994 (Proceedings of the 26th Annual ACM Symposium on Theory of Computing), 422–431쪽 — 학회판 제목은 「.879-approximation algorithms for MAX CUT and MAX 2SAT」준정부호 계획법으로 최대 절단 문제를 최적의 약 0.878 배까지 근사하는 알고리즘을 내놓은 논문이다. 유일 게임 추측(khot-2002)이 참이면 이 비율이 다항 시간으로 얻을 수 있는 최선이라고 알려져 있다. NP-난해 문제의 근사 가능성이 어디에서 끊기는지를 다루는 글에 필요하다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 서지를 확인했다(본문은 열지 못함).