@ARTICLE{lieber:algorithms,
AUTHOR = "Karl J. Lieberherr",
TITLE = "Algorithmic extremal problems
in combinatorial optimization",
JOURNAL = "Journal of Algorithms",
YEAR = 1982,
PAGES = "225-244",
VOLUME = 3,
NUMBER = 3
}

Paper.

Notes by Karl:

P-Optimal Approximation

Many approximation algorithms for generalized satisfiability
have been designed since 
1982 but they have not been compared with the performance of MAXMEAN*
and its variants.