Báo cáo toán học: " On the Approximability of Max-Cut"
Chúng tôi giới thiệu tỷ lệ hiệu suất gần như chắc chắn của một thuật toán xấp xỉ cho một vấn đề tối ưu hóa rời rạc và xem xét vấn đề MAX-CUT. Được biết rằng MAX-CUT không thể được giải quyết bởi một thuật toán xấp xỉ thời gian đa thức...