Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
1  
An LP is an optimization also: $\max c^\top x$ such that $Ax \le b$ –  Suresh Venkat Apr 30 at 23:22
1  
Yeah, but the usual notions of approximation don't apply. What if the optimal objective value is zero? What if it's negative? –  JɛffE May 1 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 at 17:35
    
Could you refer me to a proof that LP is $\mathbf{P}$-complete? All I could find was a paper ("Linear Programming is Log-Space Hard for $\mathbf{P}$", by Dobkin, Lipton and Rice) which proves $\mathbf{P}$-Hardness but not $\mathbf{P}$-Completeness. (Oh, and Wikipedia does not count.) –  Alan Sz 5 hours ago

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.