Hot answers tagged

8 votes

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

I'm not sure if you would consider the algorithms I'll discuss here "Simplex-like" (but see the comment about column generation at the end). If you have a weak separation oracle for a ...
Neal Young's user avatar
  • 10.1k
4 votes

Complexity of simplex method

It could be that the variants refer to two different forms of Linear Programs. Simplex only works with problems in Standard Equality Form (SEF) which is of the form $$\min c^T x\,\,\,\,\text{s.t.}\,\,\...
NaturalLogZ's user avatar
2 votes

The Average-case Complexity of Simplex Algorithm

The first thing that comes to mind is "Smoothed Analysis" of Spielman and Teng: Their main result is Theorem 5.0.1, which bounds the expected (over "typical instances") ...
Aryeh's user avatar
  • 10.5k
1 vote

Enumerate all allocations of points in a simplex

I'd suggest using a recursive search. Suppose you have a subset of $k$ of the points and a proposed allocation for those $k$ points into X/Y/Z. Then you can test whether there exists $w_x,w_y,w_z$ ...
D.W.'s user avatar
  • 12k

Only top scored, non community-wiki answers of a minimum length are eligible