Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.