# Questions tagged [simplex]

The tag has no usage guidance.

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
102 views

### Higher dimensional automata?

An NFA is just the data of a labelled, directed multigraph with a accepting predicate over the vertices. Simplicial sets generalize directed multigraphs by allowing the existence of higher dimensional ...
193 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 ...
• 1,216
87 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 ...
267 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 ...
• 131
1 vote
116 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 ...
1 vote
359 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 ...
• 13k
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. ...
• 157