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?

  • 1
    $\begingroup$ An LP is an optimization also: $\max c^\top x$ such that $Ax \le b$ $\endgroup$ – Suresh Venkat Apr 30 '14 at 23:22
  • 1
    $\begingroup$ Yeah, but the usual notions of approximation don't apply. What if the optimal objective value is zero? What if it's negative? $\endgroup$ – Jeffε May 1 '14 at 0:24
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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