Bài giảng Thuật toán nâng cao - Chương 11: Thuật toán xấp xỉ - Nguyễn Thanh Bình

Thuật toán xấp xỉ (approximation algorithms) B Giải quyết các bài toán NP-đầy đủ

Thuật toán hàm mũ = Thuật toán quay lại = Không hiệu quả

Thuật toán xấp xỉ

Cho kết quả gần đúng B Độ phức tạp hám đa thức

Thuật toán cho kết quá gần với kết quả tối ưu được gọi là thuật toán xấp xã