Tight approximability of MAX 2-SAT and relatives, under UGC.

Joshua Brakensiek, Neng Huang, Uri Zwick

Browse the full SODA paper archive.