Advertisement
Published in:
2009 | OriginalPaper | Chapter
Fast and Accurate Bounds on Linear Programs
Authors : Ernst Althaus, Daniel Dumitriu
Published in: Experimental Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present an algorithm that certifies the feasibility of a linear program while using rational arithmetic as little as possible. Our approach relies on computing a feasible solution of the linear program that is as far as possible from satisfying an inequality at equality. To realize such an approach, we have to detect the set of inequalities that can only be satisfied at equality.
Compared to previous approaches for this problem our algorithm has a much higher rate of success.