L. Trevisan and F. Xhafa.
The Parallel Complexity of Positive Linear Programming.
Submitted, January 1997.
- Abstract
- In this paper we study the parallel complexity of Positive Linear
Programming (PLP), i.e. the special case of Linear Programming in
packing/covering form where the input constraint matrix and constraint
vector consist entirely of positive entries. We show that the problem
of exactly solving PLP is P-complete.