@ARTICLE{lieber-specker:partial-1,
TITLE = "Complexity of Partial Satisfaction",
AUTHOR = "Karl J. Lieberherr and
Ernst Specker",
JOURNAL = "Journal of the ACM",
YEAR = 1981,
PAGES = "411-421",
VOLUME = 28,
NUMBER = 2
}

Paper.

Notes by Karl:

P-Optimal Approximation

The Journal of the ACM paper is the original paper
on P-Optimal Algorithms for constraint satisfaction problems 
(an early version of the JACM paper appeared at FOCS 1979).
The term "P-optimal" does not appear in this paper
but it was introduced in:

@ARTICLE{lieber:P-optimal, 
AUTHOR = "Karl Lieberherr",
TITLE = "P-Optimal Heuristics", 
JOURNAL = "Theoretical Computer Science",
YEAR = 1980, 
PAGES = "123-131",
VOLUME = 10 
}

For an explanation of P-optimal see the 

P-Optimal Home page.


The JACM paper uses algorithms that look artificial and seem to have
limited applicability. This was corrected in the follow-on

Paper in the Journal of Algorithms.

Also see the generalization:

Complexity of Partial Satisfaction II.