An Optimality of the Transposition Rule (Title in journal: A Transposition Rule Analysis Based on a Particle Process)

Transposition rule is a algorithm for organizing linear lists. Upon a request for a given item, the item is transposed with the preceding one. The cost of a request is the distance of the requested item from the beginning of the list. An optimality of the rule with the respect to the optimal static arrangement is demonstrated for a wide class of request distribution.

By: David Gamarnik, Petar Momcilovic

Published in: Journal of Applied Probability, volume 42, (no 1), pages 235-46 in 2005

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .