@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
}
Notes by Karl:
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.