In the eighties, when Steve was a sophomore at Princeton, we wrote a paper on how to approximate the P-optimal thresholds using linear programming.

@ARTICLE{lieber-vavasis:dortmund, AUTHOR = "Karl J. Lieberherr and S. Vavasis", TITLE = "Analysis of polynomial approximation algorithms for constraint expressions", JOURNAL = lncs, YEAR = 1983, PAGES = "187-197", VOLUME = 145, NOTE="6th Gl-Conference Dortmund, January 5-7" }

Discussion: We need the full technical report from Princeton that contains the proofs. Here it is: http://www.ccs.neu.edu/research/demeter/biblio/vavasis-tr302.html