L. Trevisan.
Positive Linear Programming, Parallel Approximation, and PCP's.
In Proceedings of the 4th European Symposium on Algorithms (ESA'96),
LNCS 1136, Springer-Verlag, pages 62-75, 1996.
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 parallel approximation algorithms by showing how to convert certain linear programming relaxations into essentially equivalent positive linear programming 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.