Algorithmic Aspects of the Internet
The goal of this thesis is to use and advance the techniques
developed in the field of exact and approximation algorithms for
many of the problems arising in the context of the Internet.
We will formalize the method of dual fitting and the idea of
factor-revealing LP. We use this combination to design and analyze
two greedy algorithms for the metric uncapacitated facility
location problem. Their approximation factors are 1.861 and 1.61
We also provide the first polynomial time algorithm for the linear
version of a market equilibrium model defined by Irving Fisher in
1891. Our algorithm is modeled after Kuhn's primal-dual algorithm
for bipartite matching.
We also study the connectivity properties of the Internet graph
and its impact on its structure. In particular, we consider the
model of growth with preferential attachment for modeling the
graph of the Internet and prove that under some reasonable
assumptions, this graph has a constant conductance.
Advisor:Ding, Yan; Randall, Dana; Vazirani, Vijay; Mihail, Milena; Duke, Richard
School:Georgia Institute of Technology
School Location:USA - Georgia
Source Type:Master's Thesis
Keywords:algorithms combinatorics and optimization
Date of Publication:07/12/2004