C.E. Groenland
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
4 records found
1
Does LRU always outperform FIFO?
A mathematical and simulation-based approach to identify better performing caching algorithms
Caching plays a crucial role in keeping the internet accessible. Many algorithms exist to determine which page should be evicted from the cache, but most analyses of these algorithms only focus on the competitive ratio. The competitive ratio, however, cannot identify which algorithm performs well in practice and which only performs well on paper.
The goal of this research is to study how the performance of deterministic and randomized caching algorithms can be compared, and how the algorithms behave on differently structured request sequences. A purely mathematical analysis is combined with simulations of uniformly random, recency-based, and favorite element request sequences.
Sleator and Tarjan [6] claim that the FIFO and LRU algorithms are competitive and provide a proof for the LRU algorithm. This research provides a proof for the competitiveness of the FIFO algorithm.
In addition, Panagiotou and Souza [4] use the characteristic vector to determine the number of cache misses for LRU. This research shows that for the FIFO algorithm, both an upper and lower bound can be obtained by using the characteristic vector.
Finally, simulations show that different request structures lead to different well-performing algorithms. The LFU algorithm, although not competitive, performs best on the favorite element request sequences, while LRU performs best on random and recency-based request sequences.
More broadly, the results show that a higher cache size yields a higher ratio of the number of cache misses for the algorithms and optimal solution, while a larger universe leads to a lower ratio. ...
The goal of this research is to study how the performance of deterministic and randomized caching algorithms can be compared, and how the algorithms behave on differently structured request sequences. A purely mathematical analysis is combined with simulations of uniformly random, recency-based, and favorite element request sequences.
Sleator and Tarjan [6] claim that the FIFO and LRU algorithms are competitive and provide a proof for the LRU algorithm. This research provides a proof for the competitiveness of the FIFO algorithm.
In addition, Panagiotou and Souza [4] use the characteristic vector to determine the number of cache misses for LRU. This research shows that for the FIFO algorithm, both an upper and lower bound can be obtained by using the characteristic vector.
Finally, simulations show that different request structures lead to different well-performing algorithms. The LFU algorithm, although not competitive, performs best on the favorite element request sequences, while LRU performs best on random and recency-based request sequences.
More broadly, the results show that a higher cache size yields a higher ratio of the number of cache misses for the algorithms and optimal solution, while a larger universe leads to a lower ratio. ...
Caching plays a crucial role in keeping the internet accessible. Many algorithms exist to determine which page should be evicted from the cache, but most analyses of these algorithms only focus on the competitive ratio. The competitive ratio, however, cannot identify which algorithm performs well in practice and which only performs well on paper.
The goal of this research is to study how the performance of deterministic and randomized caching algorithms can be compared, and how the algorithms behave on differently structured request sequences. A purely mathematical analysis is combined with simulations of uniformly random, recency-based, and favorite element request sequences.
Sleator and Tarjan [6] claim that the FIFO and LRU algorithms are competitive and provide a proof for the LRU algorithm. This research provides a proof for the competitiveness of the FIFO algorithm.
In addition, Panagiotou and Souza [4] use the characteristic vector to determine the number of cache misses for LRU. This research shows that for the FIFO algorithm, both an upper and lower bound can be obtained by using the characteristic vector.
Finally, simulations show that different request structures lead to different well-performing algorithms. The LFU algorithm, although not competitive, performs best on the favorite element request sequences, while LRU performs best on random and recency-based request sequences.
More broadly, the results show that a higher cache size yields a higher ratio of the number of cache misses for the algorithms and optimal solution, while a larger universe leads to a lower ratio.
The goal of this research is to study how the performance of deterministic and randomized caching algorithms can be compared, and how the algorithms behave on differently structured request sequences. A purely mathematical analysis is combined with simulations of uniformly random, recency-based, and favorite element request sequences.
Sleator and Tarjan [6] claim that the FIFO and LRU algorithms are competitive and provide a proof for the LRU algorithm. This research provides a proof for the competitiveness of the FIFO algorithm.
In addition, Panagiotou and Souza [4] use the characteristic vector to determine the number of cache misses for LRU. This research shows that for the FIFO algorithm, both an upper and lower bound can be obtained by using the characteristic vector.
Finally, simulations show that different request structures lead to different well-performing algorithms. The LFU algorithm, although not competitive, performs best on the favorite element request sequences, while LRU performs best on random and recency-based request sequences.
More broadly, the results show that a higher cache size yields a higher ratio of the number of cache misses for the algorithms and optimal solution, while a larger universe leads to a lower ratio.
The domination game is a two-player game played on a graph. The players have two roles, Dominator and Staller. Dominator wants to finish the game as soon as possible, while Staller tries to postpone the end of the game for as long as possible. The two players alternate turns and each turn they pick a vertex, and color the vertex itself and its neighbors. The players should always color at least one previously uncolored vertex. When all vertices are colored the game is finished. Calculating bounds on the total number of moves under optimal play for all graphs with n vertices is a hard open problem. In this research, the domination game on a specific family of graphs is analyzed, the king graphs. These are modeled after how kings move on a chessboard and provide an interesting graph with a lot of structure, but nontrivial optimal winning strategies.
For small boards, we found the optimal move counts with computer search for up to 9 x 9 boards. For general n, lower and upper bounds on the number of moves were found. For an n x n king graph, the number of moves under optimal play, gamma_g(G_n), satisfies
2/10n^2 - O(n) <= gamma_g(G_n) <= 2/9 n^2 + O(n). ...
For small boards, we found the optimal move counts with computer search for up to 9 x 9 boards. For general n, lower and upper bounds on the number of moves were found. For an n x n king graph, the number of moves under optimal play, gamma_g(G_n), satisfies
2/10n^2 - O(n) <= gamma_g(G_n) <= 2/9 n^2 + O(n). ...
The domination game is a two-player game played on a graph. The players have two roles, Dominator and Staller. Dominator wants to finish the game as soon as possible, while Staller tries to postpone the end of the game for as long as possible. The two players alternate turns and each turn they pick a vertex, and color the vertex itself and its neighbors. The players should always color at least one previously uncolored vertex. When all vertices are colored the game is finished. Calculating bounds on the total number of moves under optimal play for all graphs with n vertices is a hard open problem. In this research, the domination game on a specific family of graphs is analyzed, the king graphs. These are modeled after how kings move on a chessboard and provide an interesting graph with a lot of structure, but nontrivial optimal winning strategies.
For small boards, we found the optimal move counts with computer search for up to 9 x 9 boards. For general n, lower and upper bounds on the number of moves were found. For an n x n king graph, the number of moves under optimal play, gamma_g(G_n), satisfies
2/10n^2 - O(n) <= gamma_g(G_n) <= 2/9 n^2 + O(n).
For small boards, we found the optimal move counts with computer search for up to 9 x 9 boards. For general n, lower and upper bounds on the number of moves were found. For an n x n king graph, the number of moves under optimal play, gamma_g(G_n), satisfies
2/10n^2 - O(n) <= gamma_g(G_n) <= 2/9 n^2 + O(n).
The problem of finding even cycles efficiently in a directed graph can be rewritten to a problem of finding the permanent and determinant of the graph’s adjacency matrix. Although this has been known for a long time, it did not solve the shortest even cycle problem, as mathematicians lacked an efficient method to compute the permanent.
In 1979 Valiant found out that in some specific cases, when one works modulo a power of 2, the permanent could be computed efficiently. Although this did not directly lead to a breakthrough in finding even cycles, it laid the groundwork for Björklund, Husfeldt and Kaski to solve the problem of finding the shortest even cycle. Instead of working with the integers modulo 2, Björklund, Husfeldt and Kaski used a polynomial quotient ring E4d , which is an extension of some polynomial quotient ring F2d . The polynomial quotient ring E4d , it turns out, benefits from having a characteristic of four and relies on F2d being a field. Surprisingly, these two properties are exactly what is needed to efficiently compute both the permanent and determinant.
The aim of this thesis is to give the reader a better understanding of the polynomial quotient rings F2d and E4d that are used by Björklund, Husfeldt and Kaski in. These structures are then used to explain the part of their algorithm that computes the determinant of matrices with entries in E4d . The reader is given a deeper insight into the algorithm by comparing it to the standard algorithm for computing the determinant learned in most linear algebra classes. By using the polynomial rings and algorithm for the determinant a Python script is written. This script can perform calculations within E4d and compute the determinant for a matrix with entries in E4d . Finally, the difference between computing the permanent and the determinant will be briefly explained.
...
In 1979 Valiant found out that in some specific cases, when one works modulo a power of 2, the permanent could be computed efficiently. Although this did not directly lead to a breakthrough in finding even cycles, it laid the groundwork for Björklund, Husfeldt and Kaski to solve the problem of finding the shortest even cycle. Instead of working with the integers modulo 2, Björklund, Husfeldt and Kaski used a polynomial quotient ring E4d , which is an extension of some polynomial quotient ring F2d . The polynomial quotient ring E4d , it turns out, benefits from having a characteristic of four and relies on F2d being a field. Surprisingly, these two properties are exactly what is needed to efficiently compute both the permanent and determinant.
The aim of this thesis is to give the reader a better understanding of the polynomial quotient rings F2d and E4d that are used by Björklund, Husfeldt and Kaski in. These structures are then used to explain the part of their algorithm that computes the determinant of matrices with entries in E4d . The reader is given a deeper insight into the algorithm by comparing it to the standard algorithm for computing the determinant learned in most linear algebra classes. By using the polynomial rings and algorithm for the determinant a Python script is written. This script can perform calculations within E4d and compute the determinant for a matrix with entries in E4d . Finally, the difference between computing the permanent and the determinant will be briefly explained.
...
The problem of finding even cycles efficiently in a directed graph can be rewritten to a problem of finding the permanent and determinant of the graph’s adjacency matrix. Although this has been known for a long time, it did not solve the shortest even cycle problem, as mathematicians lacked an efficient method to compute the permanent.
In 1979 Valiant found out that in some specific cases, when one works modulo a power of 2, the permanent could be computed efficiently. Although this did not directly lead to a breakthrough in finding even cycles, it laid the groundwork for Björklund, Husfeldt and Kaski to solve the problem of finding the shortest even cycle. Instead of working with the integers modulo 2, Björklund, Husfeldt and Kaski used a polynomial quotient ring E4d , which is an extension of some polynomial quotient ring F2d . The polynomial quotient ring E4d , it turns out, benefits from having a characteristic of four and relies on F2d being a field. Surprisingly, these two properties are exactly what is needed to efficiently compute both the permanent and determinant.
The aim of this thesis is to give the reader a better understanding of the polynomial quotient rings F2d and E4d that are used by Björklund, Husfeldt and Kaski in. These structures are then used to explain the part of their algorithm that computes the determinant of matrices with entries in E4d . The reader is given a deeper insight into the algorithm by comparing it to the standard algorithm for computing the determinant learned in most linear algebra classes. By using the polynomial rings and algorithm for the determinant a Python script is written. This script can perform calculations within E4d and compute the determinant for a matrix with entries in E4d . Finally, the difference between computing the permanent and the determinant will be briefly explained.
In 1979 Valiant found out that in some specific cases, when one works modulo a power of 2, the permanent could be computed efficiently. Although this did not directly lead to a breakthrough in finding even cycles, it laid the groundwork for Björklund, Husfeldt and Kaski to solve the problem of finding the shortest even cycle. Instead of working with the integers modulo 2, Björklund, Husfeldt and Kaski used a polynomial quotient ring E4d , which is an extension of some polynomial quotient ring F2d . The polynomial quotient ring E4d , it turns out, benefits from having a characteristic of four and relies on F2d being a field. Surprisingly, these two properties are exactly what is needed to efficiently compute both the permanent and determinant.
The aim of this thesis is to give the reader a better understanding of the polynomial quotient rings F2d and E4d that are used by Björklund, Husfeldt and Kaski in. These structures are then used to explain the part of their algorithm that computes the determinant of matrices with entries in E4d . The reader is given a deeper insight into the algorithm by comparing it to the standard algorithm for computing the determinant learned in most linear algebra classes. By using the polynomial rings and algorithm for the determinant a Python script is written. This script can perform calculations within E4d and compute the determinant for a matrix with entries in E4d . Finally, the difference between computing the permanent and the determinant will be briefly explained.
Master thesis
(2024)
-
L.K.M. Verlinde, C.E. Groenland, A. Bishnoi, D.C. Gijswijt, J.M.A.M. van Neerven
Consider an arbitrary finite grid in some field. How many hyperplanes are required so that every point is contained in at least k hyperplanes, except for one point that is not allowed to be contained in any hyperplane? To solve this so-called hyperplane grid covering problem, the polynomial method has proven to be extremely useful in finding bounds on the minimum number of hyperplanes required. This has given rise to a second problem: the polynomial grid covering problem. This problem considers the minimum degree of a polynomial such that every grid point is a root with multiplicity k, except for one point where the polynomial does not vanish. We study these two related problems for multiple grids: the hypercube, the vector space over the binary field and grids in the Cartesian plane. Since polynomial covers in the latter have not been studied before, we provide algorithms and techniques to study these covers. We also explore the link between grid coverings and two results from algebraic geometry: the Footprint Bound and the Cayley-Bacharach Theorems.
...
Consider an arbitrary finite grid in some field. How many hyperplanes are required so that every point is contained in at least k hyperplanes, except for one point that is not allowed to be contained in any hyperplane? To solve this so-called hyperplane grid covering problem, the polynomial method has proven to be extremely useful in finding bounds on the minimum number of hyperplanes required. This has given rise to a second problem: the polynomial grid covering problem. This problem considers the minimum degree of a polynomial such that every grid point is a root with multiplicity k, except for one point where the polynomial does not vanish. We study these two related problems for multiple grids: the hypercube, the vector space over the binary field and grids in the Cartesian plane. Since polynomial covers in the latter have not been studied before, we provide algorithms and techniques to study these covers. We also explore the link between grid coverings and two results from algebraic geometry: the Footprint Bound and the Cayley-Bacharach Theorems.