# 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
• OP, as Suresh points out, the answer to your question will depend on what kind of approximation you ask about Can you clarify what you have in mind? – Neal Young May 2 at 1:41
• The feasibility problem with no objective is already P-complete. Adding in the promise that a feasible solution exists does nothing to help identify a solution, as otherwise the prover can guess that a solution exists and work from there. It's hard to imagine a particularly useful objective function / approximation guarantee pair we can tack on to an already P-complete problem that suddenly makes the problem not P-hard. – Yonatan N May 5 at 21:30

## 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.