@TECHREPORT{CPS-II-rep,
AUTHOR = "Karl Lieberherr and Ernst Specker",
TITLE = "Complexity of Partial Satisfaction II",
INSTITUTION = "Princeton University, Dept. of EECS",
YEAR = 1982,
NUMBER = "293",
Note = "http://www.ccs.neu.edu/research/demeter/biblio/partial-sat-II.html"
}

@UNPUBLISHED{lieber-specker:partial-2,
TITLE = "Complexity of Partial Satisfaction II",
AUTHOR = "Karl J. Lieberherr and Ernst Specker",
YEAR = 1985 
}

Papers.

Notes by Karl:

P-Optimal Approximation

A follow-on paper to the Journal of the ACM paper.
Indicates that determining the P-optimal thresholds 
requires ingenuity. Presents the results of the JACM
paper in a general context.

The paper exists in two incarnations, one from January 1982 and one from 1985.
Partial-SAT2.pdf is the newer version from 1985 and complexity.pdf is
the older version from 1982 (Princeton Unversity Technical Report).

Both versions contain valuable information. For example, the older version
contains a section 6 about solving minmax problems which is omitted from
the later version.

The paper was submitted to the SIAM Journal on Computing and we got back the following wonderful review:

This seems to be the ultimate result along the cores of research of Lieberherr/Specker.
It gives a closed form to a natural problem which is stated in a way which makes its
significance to complexity theory clear. The theorme's proof is a beautiful and tricky
kind of good mathematics and a brilliant example of good math,
rightly applied in computer science. Also very well written.

The paper is not well written. I had tremendous difficulty
trying to understand certain points.