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 reports@us.ibm.com .