<p>My first observation: we know how to solve <a href="http://pubsonline.informs.org/doi/abs/10.1287/opre.34.2.250" rel="nofollow">your LPs in strongly polynomial time</a>, but this is an open question for general LPs.</p>

CC BY-SA 3.0
2014-01-23T19:13:02.327Z
2014-01-23T19:13:02.327Z
Austin Buchanan
<p>We have a linear program in the standard form $Ax=b,x\geq 0$ with $A(i,j)\in\{-1,0,1\}\:\forall\,i,j$ and $b(i)\in\{0,1\}\:\forall\,i$. $A$ is not full rank. Is the time complexity of testing the feasibility of this LP any better than that of general LPs? If yes, is there an algorithm known? Thanks in advance.</p>

<cc.complexity-theory><linear-programming>
Testing feasibility of special linear programs
Pawan Aurora
# Testing feasibility of special linear programs

(Asked by: username_0 on 2014-01-23)

We have a linear program in the standard form $Ax=b,x\geq 0$ with $A(i,j)\in\{-1,0,1\}\:\forall\,i,j$ and $b(i)\in\{0,1\}\:\forall\,i$. $A$ is not full rank. Is the time complexity of testing the feasibility of this LP any better than that of general LPs? If yes, is there an algorithm known? Thanks in advance.

**Tags:** cc.complexity-theory, linear-programming


---

## 1 answers

### Answer by username_1 on 2014-01-23. Score: 3

My first observation: we know how to solve [your LPs in strongly polynomial time](http://pubsonline.informs.org/doi/abs/10.1287/opre.34.2.250), but this is an open question for general LPs.


---

