✦ LIBER ✦

Off-line algorithms for the list update problem

✍ Scribed by Nick Reingold; Jeffery Westbrook

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 637 KB
Volume: 60
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(96)00144-5

No coin nor oath required. For personal study only.

✦ Synopsis

Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum algorithms are given; these lead to optimum algorithm which runs in time 02"( n -1) !m, where n is the length of the list and m is the number of requests. The previous best algorithm, an adaptation of a more general algorithm due to Manasse et al. (1988), runs in time O(n!)*m.

📜 SIMILAR VOLUMES

Revisiting the COUNTER algorithms for li

Revisiting the COUNTER algorithms for list update

✍ Susanne Albers; Michael Mitzenmacher 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 579 KB

A combined BIT and TIMESTAMP algorithm f

A combined BIT and TIMESTAMP algorithm for the list update problem

✍ Susanne Albers; Bernhard von Stengel; Ralph Werchner 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 477 KB

A faster off-line algorithm for the TCP

A faster off-line algorithm for the TCP acknowledgement problem

✍ John Noga; Steve Seiden; Gerhard J. Woeginger 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 48 KB

In a recent paper [Proceedings of STOC'98, 1998, pp. 389-398], Dooly, Goldman and Scott study a problem that is motivated by the networking problem of dynamically adjusting delays of acknowledgements in the Transmission Control Protocol (TCP). Among other results, they give an O(n 2 ) off-line algor

A lower bound for randomized list update

A lower bound for randomized list update algorithms

✍ Boris Teia 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 405 KB

Competitive Algorithms for Relaxed List

Competitive Algorithms for Relaxed List Update and Multilevel Caching

✍ Marek Chrobak; John Noga 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 188 KB

We study relaxed list update problem RLUP , in which access requests are made to items stored in a list. The cost to access the jth item x is c , where j j c F c for all i. After the access, x can be repeatedly swapped, at no cost, with i i q1 j any item that precedes it in the list. This problem w

On lookahead in the list update problem

✍ Rahul Simha; Amitava Majumdar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 593 KB