Analyzing self-adjusting linear list algorithms with deletions and unsuccessful searches

Autor:	Charles U. Martel, Lucas Chi Kwong Hui
Rok vydání:	1996
Předmět:	Large class Theoretical computer science Competitive analysis Computer science Self adjusting computer.software_genre Data structure Computer Science Applications Theoretical Computer Science Signal Processing Data mining Algorithm computer Information Systems
Zdroj:	Information Processing Letters. 58:231-236
ISSN:	0020-0190
DOI:	10.1016/0020-0190(96)00064-6
Popis:	In (Hui and Martel, 1993), we designed and analyzed efficient self-adjusting linear list algorithms. Our analysis proves that a self-adjusting linear list algorithm, MP, is competitive to a large class of offline adversaries, where the operations are successful searches, unsuccessful searches, and insertions. Analysis of deletions is listed as an open question. This paper presents an improved version of MP which is also able to handle deletions efficiently, and proves that the new MP algorithm is 6-competitive to offline adversaries when considering successful searches, unsuccessful searches, insertions, and deletions.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::cd10dcc731b62c830cb38e173f2a5990 https://doi.org/10.1016/0020-0190(96)00064-6 Zobrazit plný text záznamu Full Text from ScienceDirect