4.2 Article

On list update with locality of reference

期刊

JOURNAL OF COMPUTER AND SYSTEM SCIENCES
卷 82, 期 5, 页码 627-653

出版社

ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2015.11.005

关键词

Data structures; Self-organizing lists; Online algorithms; Competitive analysis; Locality of reference

向作者/读者索取更多资源

We present a comprehensive study of the list update problem with locality of reference. More specifically, we present a combined theoretical and experimental study in which the theoretically proven and experimentally observed performance guarantees of algorithms match or nearly match. Firstly, we introduce a new model of locality of reference that closely captures the concept of runs. Using this model we develop refined theoretical analyses of popular list update algorithms. Secondly, we present an extensive experimental study in which we have tested the algorithms on traces from benchmark libraries. The theoretical and experimental bounds differ by just a few percent. Our new theoretical bounds are substantially lower than those provided by standard competitive analysis. It shows that the well-known Move-To-Front strategy exhibits the best performance. Its refined competitive ratio tends to 1 as the degree of locality increases. This confirms that Move-To-Front is the method of choice in practice. (C) 2015 Elsevier Inc. All rights reserved.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.2
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
Article Computer Science, Hardware & Architecture

Solving problems on generalized convex graphs via mim-width

Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro, Daniel Paulusma

Summary: This article discusses the convexity and mim-width of bipartite graphs, and it proves that for certain families of graphs 7-t, the 7-t-convex graphs can be solved in polynomial time for NP-complete problems. It also explores the bounded and unbounded mim-width of 7-t-convex graphs for different sets 7-t.

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2024)

Article Computer Science, Hardware & Architecture

Performance modeling and analysis for randomly walking mobile users with Markov chains

Keqin Li

Summary: In this paper, we propose a computation offloading strategy to satisfy all UEs served by an MEC and develop an efficient method to find such a strategy. By using Markov chains to characterize UE mobility and calculating the joint probability distribution of UE locations, we can obtain the average response time of UEs and predict the overall average response time of tasks. Additionally, we solve the power constrained MEC speed setting problem.

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2024)

Correction Computer Science, Hardware & Architecture

Prediction, learning, uniform convergence, and scale-sensitive dimensions (vol 56, pg 174, 1998)

Peter L. Bartlett, Philip M. Long

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2024)

Article Computer Science, Hardware & Architecture

Fast and succinct population protocols for Presburger arithmetic

Philipp Czerner, Roland Guttenberg, Martin Helfrich, Javier Esparza

Summary: This paper presents a construction method that produces population protocols with a small number of states, while achieving near-optimal expected number of interactions, for deciding Presburger predicates.

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2024)

Article Computer Science, Hardware & Architecture

Orienting undirected phylogenetic networks

Katharina T. Huber, Leo van Iersel, Remie Janssen, Mark Jones, Vincent Moulton, Yukihiro Murakami, Charles Semple

Summary: This paper investigates the relationship between undirected and directed phylogenetic networks, and provides corresponding algorithms. The study reveals that the directed phylogenetic network is unique under specific conditions. Additionally, an algorithm for directing undirected binary networks is described, applicable to certain classes of directed phylogenetic networks.

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2024)

Article Computer Science, Hardware & Architecture

Wireless IoT sensors data collection reward maximization by leveraging multiple energy- and storage-constrained UAVs

Francesco Betti Sorbelli, Alfredo Navarra, Lorenzo Palazzetti, Cristina M. Pinotti, Giuseppe Prencipe

Summary: This study discusses the deployment of IoT sensors in an area that needs to be monitored. Drones are used to collect data from the sensors, but they have energy and storage constraints. To maximize the overall reward from the collected data and ensure compliance with energy and storage limits, an optimization problem called Multiple-drone Data-collection Maximization Problem (MDMP) is proposed and solved using an Integer Linear Programming algorithm.

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2024)

Article Computer Science, Hardware & Architecture

On the complexity of the storyplan problem

Carla Binucci, Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nollenburg, Antonios Symvonis

Summary: In this study, we investigate the problem of representing a graph as a storyplan, which is a model for dynamic graph visualization. We prove the NP-completeness of this problem and propose two parameterized algorithms as solutions. We also demonstrate that partial 3-trees always admit a storyplan and can be computed in linear time. Additionally, we show that even if the vertex appearance order is given, the problem of choosing how to draw the frames remains NP-complete.

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2024)

Article Computer Science, Hardware & Architecture

Perpetual maintenance of machines with different urgency requirements

Leszek Gasieniec, Tomasz Jurdzinski, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, Tomasz Radzik

Summary: This passage describes the Bamboo Garden Trimming Problem and presents approximation algorithms for both Discrete BGT and Continuous BGT.

JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2024)