Competitive Paging and Dual-Guided On-Line Weighted Caching and Matching Algorithms (Thesis)

Abstract:

This thesis presents research done by the author on competitive analysis of on-line problems. An on-line problem is a problem that is given and solved one piece at a time. An on-line strategy for solving such a problem must give the solution to each piece knowing only the current piece and preceding pieces, in ignorance of the pieces to be given in the future. We consider on-line strategies that are competitive (guaranteeing solutions whose costs are within a constant factor of optimal) for several combinatorial optimization problems: paging, weight caching, the k-server problem, and weighted matching. We introduce variations on the standard model of competitive analysis for paging: allowing randomization, allowing resource-bounded lookahead, and loose competitiveness, in which performance over a range of fast memory sizes is considered and noncompetitiveness is allowed provided the fault rate is insignificant. Each variation leads to substantially better competitive ratios. We present a general technique for competitive analysis of linear optimization problems: competitive analyses are obtained by using linear programming duality to obtain bounds on the optimal cost. The technique is implicit in previous work on paging, weighted caching, and weighted matching. We generalize the implicit previous use of the technique, obtaining the greedy dual algorithm for weighted caching. The strategy generalizes the least-recently-used and first-in-first-out algorithms for paging and the balance algorithm for weighted caching. The analysis strengthens a previous analysis of the balance algorithm for weighted caching. We explore the linear programming dual of the k-server problem, showing that the k-server problem is a special case of on-line minimum-weight matching, revealing close relationships between on-line weighted caching and assignment algorithms, and showing how duality can yield potential function analyses.