Results on Approximation Algorithms (Thesis)
Report ID: TR-625-00Author: Karakostas, George
Date: 2000-11-00
Pages: 118
Download Formats: |PDF| |Postscript|
Abstract:
This thesis presents approximation algorithms for three problems: the Minimum Latency Tour problem, the $k$-Minimum Spanning Tree problem on graphs and the implementation of the Perfect-LFU (Least Frequently Used) policy for Web caching.
The Minimum Latency Tour problem, also known as the traveling repairman problem, is a variant of the Traveling Salesman Problem. We are given a graph with non-negative edge weights and a starting node and the goal is to compute a tour on the graph that visits all the nodes and minimizes the sum of the arrival times at the other nodes. The first part of this thesis presents a quasipolynomial-time approximation scheme for this problem when the instance is a weighted tree and when the the nodes lie in the $d$-dimensional Euclidean space for some fixed $d$. Our ideas extend to other norms as well as to the case of planar graphs. We also present a polynomial time constant factor approximation algorithm for the general metric case, which achieves a slightly worse approximation factor than the currently best known (due to M.Goemans and J.Kleinberg), but is simpler. Finally we extend the definition of the problem to a more general weighted version and show how to apply our ideas in this more general setting.
In the second part we present an approximation algorithm for the problem of finding a minimum tree spanning any $k$ vertices in a graph ($k$-MST) that achieves an approximation factor of $2+\eps$, for any arbitrary constant $\eps>0$ and runs in time $n^{O(1/\eps)}$, improving a 3-approximation algorithm by N.Garg. As in Garg's case, the algorithm extends to a (2+$\eps$)-approximation algorithm for the minimum tour that visits any $k$ vertices, provided the edge costs satisfy the triangle inequality.
The last part presents a modification of the Perfect-LFU replacement policy for Web caching called Window-LFU. Unlike Perfect-LFU, our policy can be implemented in practice, and under certain assumptions we can prove that it can approximate the hit rate of Perfect-LFU within a factor of $1-\eps$, using space polynomial on the cache size instead of polynomial on the total number of pages in the Web (which is the case for Perfect-LFU). In addition to providing analytical bounds for this new policy, we provide experimental results which show that in practice our policy performs better than expected from its analytical study. This leads to a revision of our initial assumptions about the Web. More specifically, our assumption of statistical independence among the requests in a request stream does not seem to hold. Instead, there are dependencies due to locality and our policy takes advantage of them.