Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes

Details Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes

2011-10-13

arxiv.org/abs/1110.3014v1

Computer Science

Discrete Mathematics

Scientific paper

An acyclic USO on a hypercube is formed by directing its edges in such as way that the digraph is acyclic and each face of the hypercube has a unique sink and a unique source. A path to the global sink of an acyclic USO can be modeled as pivoting in a unit hypercube of the same dimension with an abstract objective function, and vice versa. In such a way, Zadeh's 'least entered rule' and other history based pivot rules can be applied to the problem of finding the global sink of an acyclic USO. In this paper we present some theoretical and empirical results on the worst case behaviour of various history based pivot rules for this problem. In particular, we investigate whether or not they can follow a Hamiltonian path on an acyclic USO.

Affiliated with

Also associated with

No associations

Rating

Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes 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 Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Worst-case Behaviour of History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-500750