Results on Approximation Algorithms (Thesis)

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.