<p>See the paper &quot;<a href="https://doi.org/10.1145/167088.167211" rel="nofollow noreferrer">A parallel approximation algorithm for positive linear programming.</a>&quot; by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time.</p>

CC BY-SA 4.0
2021-04-30T13:30:44.397Z
For positive linear programs a more up to date paper is that of Mahoney et al which also has references to several other papers. https://drops.dagstuhl.de/opus/volltexte/2016/6333/
Chandra Chekuri
CC BY-SA 4.0
2014-05-01T01:02:59.833Z
2021-04-30T04:38:37.813Z
2021-04-30T04:38:37.813Z
David Harris
<p>It is known that Linear Programming (LP) is P-complete. 
I am interested in approximation algorithms for LP.</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-04-30T23:22:44.530Z
An LP is an optimization also: $\max c^\top x$ such that $Ax \le b$
Suresh Venkat
CC BY-SA 3.0
2014-05-01T00:24:17.997Z
Yeah, but the usual notions of approximation don't apply. What if the optimal objective value is zero? What if it's negative?
Jeffε
CC BY-SA 3.0
2014-05-01T17:35:36.250Z
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
CC BY-SA 4.0
2021-05-02T01:41:21.103Z
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
CC BY-SA 4.0
2021-05-05T21:30:15.567Z
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
<cc.complexity-theory><linear-programming><approximation-hardness><polynomial-time>
Complexity of linear programming
user0928
# Complexity of linear programming

(Asked by: username_0 on 2014-04-30)

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?

**Tags:** cc.complexity-theory, linear-programming, approximation-hardness, polynomial-time

> **Comments:**
> **username_1**: An LP is an optimization also: $\max c^\top x$ such that $Ax \le b$  
> **username_2**: Yeah, but the usual notions of approximation don't apply. What if the optimal objective value is zero? What if it's negative?  
> **username_1**: 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.  
> **username_3**: 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?  
> **username_4**: 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.  

---

## 1 answers

### Answer by username_5 on 2014-05-01. Score: 6

See the paper "[A parallel approximation algorithm for positive linear programming.](https://doi.org/10.1145/167088.167211)" by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time.

> **Comments:**
> **username_6**: For positive linear programs a more up to date paper is that of Mahoney et al which also has references to several other papers. https://drops.dagstuhl.de/opus/volltexte/2016/6333/  

---

