Competitive On-line Algorithms for Paging and Graph Coloring

TitleCompetitive On-line Algorithms for Paging and Graph Coloring
Publication TypeTechnical Report
Year of Publication1992
AuthorsIrani S
Other Numbers718
KeywordsCompetitive Analysis, locality of reference, lookahead, On-line Algorithms, on-line graph coloring, paging

We analyze the competitiveness of on-line algorithms for two problems: paging and on-line graph coloring. In the first problem, we develop a refinement of competitive analysis for paging algorithms which addresses some of the areas where traditional competitive analysis fails to represent what is observed in practice. For example, traditional competitive analysis is unable to discern between LRU and FIFO, although in practice LRU performs much better than FIFO. In addition, the theoretical competitiveness of LRU is much more pessimistic than what is observed in practice. We also address the following important question: given some knowledge of a program's reference pattern, can we use it to improve paging performance on that program?We address these concerns by introducing an important practical element that underlies the philosophy behind paging: locality of reference. We devise a graph-theoretical model, the access graph, for studying locality of reference.The second problem that we consider is on-line graph coloring. In the spirit of competitiveness, we evaluate on-line graph coloring algorithms by their performance ratio which measures the number of colors the algorithm uses in comparison to the chromatic number of the graph. We consider the class of d-inductive graphs. A graph G is d-inductive if the vertices of G can be numbered so that each vertex has at most d edges to higher numbered vertices. We analyze the greedy algorithm and show that if G is d-inductive then FF uses O( d log n) colors on G. We show that this bound is tight. Since planar graphs are 5-inductive, and chordal graphs are c(G)-inductive, (where c(G) is the chromatic number of the graph G), our results yield bounds on the performance ratio of greedy on these important classes of graphs. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookahead l, if it must color vertex i after examining only the first l+i vertices. We show that for l < (n / log n) no on-line algorithm with lookahead l can perform better than First Fit on d-inductive graphs.

Bibliographic Notes

ICSI Technical Report TR-92-013

Abbreviated Authors

S. Irani

ICSI Publication Type

Technical Report