Skip to main content

Questions tagged [simplex]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
52 votes
6 answers
31k views

Complexity of the simplex algorithm

What is the upper bound on the simplex algorithm for finding a solution to a Linear Program? How would I go about finding a proof for such a case? It seems as though the worst case is if each vertex ...
shuttle87's user avatar
  • 637
33 votes
3 answers
2k views

Consequences of existence of a strongly polynomial algorithm for linear programming?

One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and ...
Ian's user avatar
  • 2,747
18 votes
1 answer
614 views

The structure of pathological instances for simplex algorithms

As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum....
Artem Kaznatcheev's user avatar
14 votes
2 answers
2k views

Justification for the Hungarian method (Kuhn-Munkres)

I wrote an implementation of the Kuhn-Munkres algorithm for the minimum-weight bipartite perfect matching problem based on lecture notes I found here and there on the web. It works really well, even ...
user avatar
7 votes
1 answer
373 views

Is there a simplex-like algorithm that can be used with a separation oracle?

Linear programs can be solved in polynomial time using the ellipsoid method, but in practice the Simplex method is much more efficient, and the smoothed analysis framework of Spielman and Teng ...
Erel Segal-Halevi's user avatar