[erk__]

If I read the paper correctly the 2-MAXSAT problem is usually referred to as MAX-2-SAT

https://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-sat...