# Questions tagged [simplex]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
206 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 ...
1 vote
107 views

### Is this proof of $LP$ being in $coNP$ correct?

I am referring to the natural decision version of the Linear Programming problem: given $A \in \mathbb{Q}^{m \times n}, \ b \in \mathbb{Q}^m, \ c \in \mathbb{Q}^n, \ \alpha \in \mathbb{Q}$, does there ...
65 views

### Using Baire Category to analyze the efficiency of the Simplex Method

I read from the wiki page of the Simplex Algorithm that we can "use Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the ...
1 vote
252 views

### Does simplex algorithm run in polynomial on Bipartite Perfect matching polytope?

It is well known that simplex algorithm runs in exponential time in worst case. However are there situations (necessary and sufficient conditions) where simplex algorithm runs in polynomial time? In ...
1 vote
130 views

### Enumerate all allocations of points in a simplex

Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$. Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process: Fix two positive ...
1k views

### The Average-case Complexity of Simplex Algorithm

I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did ...
1 vote
577 views

### equivalent way(s) of expressing P=?NP problem in linear programming?

the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella  was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea ...
261 views

### Generating points uniformly distributed over the SURFACE of a standard simplex

I would like to generate points that are uniformly distributed over the SURFACE of a standard $k$-simplex ($k$ dimensions, $k+1$ vertices). One way to efficiently generate points that are uniformly ...
191 views

### LP-type vs. Approximation

I'm interested in an computational geometry problem that's sensibly expressed as an infinite dimensional 0-1 integer program. I'm not worried about finding an actual minimum for the objective ...
400 views

### Motivation for Developing Shortest Path Simplex Algorithms

I'm reading Efficient Shortest Path Simplex Algorithms by Donald Goldfarb, Jianxiu Hao and Shen-Roan Kai who considered "the specialization of the primal simplex algorithm to the problem of finding a ...
1 vote
241 views

### Optimizing along a cube $s=\{0,1\}^n$

I am doing an optimization on a n-dimensional cube. That means that every solution is a set of $0$ and $1$, hence $s=\{0,1\}^n$. Most optimization algorithms though need a differential to work. E.g. ...
2k views

### Best book on Simplex Method implementation?

I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in ...
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 ... 534 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....