Linear programming is $P$-complete.
However are there special situations where we know an $NC$ algorithm?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Just an aside, are there possibly schemes in which there are BFS (Breadth First Search) type searches that make for an NC algorithm? Possibly reduce search space, in special scenarios.that allow for NC algorithms. $\endgroup$– user3483902Commented Aug 22, 2017 at 10:22
-
$\begingroup$ Solving positive linear programming approximately is in NC. See for example, pdfs.semanticscholar.org/34f2/… $\endgroup$– ThatchapholCommented Aug 22, 2017 at 17:24
-
2$\begingroup$ Minimum spanning trees and shortest paths in weighted graphs are both expressible as linear programs, and have both long been known to be in NC. $\endgroup$– David EppsteinCommented Dec 28, 2017 at 6:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Fixed dimensional linear programming (for any constant dimension $d$) is known to be in $\mathsf{NC}$; in fact, it can be done work-efficiently (in the same amount of work as the fastest sequential algorithm). The more recent paper by Blelloch et al. shows that the randomized-incremental approach for constant-dimensional LP can actually be parallelized efficiently.
Alon and Meggido (1994): Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time
Blelloch et al. (2016): Parallelism in Randomized Incremental Algorithms
