The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes

Details The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes

2006-05-04

arxiv.org/abs/math/0605117v1

Mathematics

Combinatorics

31 Pages, 11 figures

Scientific paper

The simplex algorithm using the random edge pivot-rule on any realization of a dual cyclic 4-polytope with n facets does not take more than O(n) pivot-steps. This even holds for general abstract objective functions (AOF) / acyclic unique sink orientations (AUSO). The methods can be used to show analogous results for products of two polygons. In contrast, we show that the random facet pivot-rule is slow on dual cyclic 4-polytopes, i.e. there are AUSOs on which random facet takes at least \Omega(n^2) steps.

Affiliated with

Also associated with

No associations

Rating

The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-299944