# Complexity of linear programming

It is known that Linear Programming (LP) is P-complete. I am interested in approximation algorithms for LP.

There are numerous inapproximability results for NP optimization problems, e.g. it is NP-hard to achieve approximation ratio better than 7/8 for MAX-3SAT.

Are there similar P-hardness results for approximation optimization problems in P?
In particular, is it known if LP is P-hard to approximate?

• An LP is an optimization also: $\max c^\top x$ such that $Ax \le b$ – Suresh Venkat Apr 30 '14 at 23:22
• Yeah, but the usual notions of approximation don't apply. What if the optimal objective value is zero? What if it's negative? – Jeffε May 1 '14 at 0:24
• Negativity doesn't change anything if you replace the usual A/OPT by |A - OPT|/|OPT|. As for when OPT is $0$, that problem occurs even outside LPs: one response is "this shows that approximating LPs is also P-complete" and the other would be to relax to a $(\alpha, \beta)$ style approximation. – Suresh Venkat May 1 '14 at 17:35

## 1 Answer

See the paper "A parallel approximation algorithm for positive linear programming." by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time.