Questions tagged [simplex]
The simplex tag has no usage guidance.
17
questions
0
votes
0
answers
46
views
Using Simplex for Difference Logic
I'm interested in what happens when using the Simplex algorithm on Difference logic, inspired by problem 5.4 in Kroening and Strichman's Decision Procedures.
Clearly, in this case, all constraints of ...
- 161
6
votes
1
answer
351
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 ...
- 2,078
1
vote
0
answers
115
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 ...
- 89
3
votes
0
answers
82
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 ...
- 131
1
vote
0
answers
338
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 ...
- 12.8k
1
vote
2
answers
144
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 ...
- 2,078
6
votes
1
answer
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 ...
- 451
1
vote
1
answer
618
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 [1] was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea ...
- 11k
3
votes
1
answer
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
4
votes
0
answers
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,206
8
votes
1
answer
407
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 ...
- 183
1
vote
0
answers
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
14
votes
5
answers
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 ...
- 551
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 ...
quid
18
votes
1
answer
588
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....
- 10.2k
51
votes
6
answers
28k
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 ...
- 627
31
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 ...
- 2,717