L. Trevisan.<br>
<b>Positive Linear Programming, Parallel Approximation, and PCP's.</b><br>
In <i>Proceedings of the 
<a href="http://www-lsi.upc.es/~esa96/">4th European Symposium on 
Algorithms (ESA'96)</a></i>,<br>
LNCS 1136, Springer-Verlag, pages 62-75, 1996.

<dl>




<dt> <b> Abstract </b> <dd>


Several approximation algorithms for optimization problems are
based on the following paradigm: solve a
linear or semidefinite programming relaxation of the problem, then use
randomized rounding to convert fractional solutions of the relaxation
into integer solutions for the combinatorial problem. 
We demonstrate that such a paradigm can also yield <i>parallel</i>
approximation algorithms by showing how to
convert certain linear programming relaxations into essentially
equivalent <i>positive linear programming</i>  relaxations that can be
near-optimally solved in NC. Building on this technique, and finding
some new linear programming relaxations, we develop NC approximation
algorithms for Max Sat, Max Directed Cut and Max kCSP.
The algorithm for Max Sat is essentially
as good as the best known sequential algorithms. The algorithm for Max kCSP
improves of a factor of 2 on the approximation of previous sequential 
algorithms, and has consequences in the field of probabilistically 
checkable proofs.


</dl>