{"id":12633,"date":"2021-11-14T20:28:59","date_gmt":"2021-11-15T01:28:59","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12633"},"modified":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","slug":"tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-124-deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\/","title":{"rendered":"TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-124: Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/\">Technical Report<\/a> <strong>TR-124<\/strong><br>\nOctober 1987<\/p>\n\n\n\n<h2 id=\"deterministic-optimal-and-expedient-move-to-rear-list-organizing-strategies\" class=\"wp-block-heading tr_t1\">Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">B.J. Oommen, E.R. Hansen , J.I. Munro<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<p>Let lt = {R1 ,R2, &#8230; , AN} be a list of elements in which Ai is accessed with an (unknown) probability Si. To minimize the cost of accessing the elements, it is advantageous if the elements are sorted in the descending order of the access probabilities. Attempts to achieve this have been made in which a simple list reordering operation is performed on every access.<br>\nIn this paper we present two simple self-organizing strategies. The strategies are deterministic and absorbing in their Markovian representation and are completely counter-intuitive, in that they are of a Move-To-Rear (MTR) flavour. Whereas the first of the schemes requires linear space (space proportional to the number of elements in the list}, the second requires only constant space. We show that the former scheme is optimal, independent of the distribution of the access probabilities. By this we mean that although the list could converge to one of its N! configurations, by suitably performing the move-to-rear operation, the probability of converging to the right arrangement can be made as close to unity as desired. The second scheme requiring constant space is shown to be expedient. We conjecture its optimality.<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/tr-124.pdf\">TR-124.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-124 October 1987 Deterministic Optimal and Expedient Move-to-Rear List Organizing Strategies B.J. Oommen, E.R. Hansen , J.I. Munro Abstract Let lt = {R1 ,R2, &#8230; , AN} be a list of elements in which Ai is accessed with an (unknown) probability Si. To minimize the cost of accessing the elements, it [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11827,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12633","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12633","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12633"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12633\/revisions"}],"predecessor-version":[{"id":12634,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12633\/revisions\/12634"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11827"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12633"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}