Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Sign up or log in to customize your list.
By using our site, you acknowledge that you have read and understand our Cookie Policy, Privacy Policy, and our Terms of Service.
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.
My first observation: we know how to solve your LPs in strongly polynomial time, but this is an open question for general LPs.
Thanks for contributing an answer to Theoretical Computer Science Stack Exchange!
Please be sure to answer the question. Provide details and share your research!
Asking for help, clarification, or responding to other answers.
Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Not the answer you're looking for? Browse other questions tagged cc.complexity-theory linear-programming or ask your own question.
Unicorn Meta Zoo #1: Why another podcast?
What are the best possible time/error tradeoffs for approximate solution of linear programs?
How fast can we solve a totally unimodular integer linear program?
What classes of mathematical programs can be solved exactly or approximately, in polynomial time?
How to determine proper rounding in linear programming relaxations?
Linear programming with superpolynomially many constraints?
What is the definining line between a helicopter and a drone a person can ride in?
Why doesn't the university give past final exams' answers?
Has a Nobel Peace laureate ever been accused of war crimes?
IC on Digikey is 5x more expensive than board containing same IC on Alibaba: How?
Are there any AGPL-style licences that require source code modifications to be public?
What is the evidence that custom checks in Northern Ireland are going to result in violence?
Why is ArcGIS Pro not symbolizing my entire range of values?
Do chord progressions usually move by fifths?
What kind of capacitor is this in the image?
When speaking, how do you change your mind mid-sentence?
Would I be safe to drive a 23 year old truck for 7 hours / 450 miles?
Can this water damage be explained by lack of gutters and grading issues?
Why not use the yoke to control yaw, as well as pitch and roll?
A German immigrant ancestor has a "Registration Affidavit of Alien Enemy" on file. What does that mean exactly?
Is there a verb for listening stealthily?
Why are two-digit numbers in Jonathan Swift's "Gulliver's Travels" (1726) written in "German style"?
Married in secret, can marital status in passport be changed at a later date?
Why does BitLocker not use RSA?
