Algorithmic Aspects of the Internet

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/6427

Title: Algorithmic Aspects of the Internet
Author: Saberi, Amin
Abstract: 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 respectively. 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.
Type: Dissertation
URI: http://hdl.handle.net/1853/6427
Date: 2004-07-12
Publisher: Georgia Institute of Technology
Subject: Internet
Algorithms
Game theory
Internet programming
Game theory
Computer networks Scalability
Algorithms
Department: Algorithms, Combinatorics, and Optimization
Computing
Advisor: Committee Co-Chairs: Milena Mihail ; Vijay Vazirani ; Committee Members: Yan Ding ; Richard Duke ; Dana Randall
Degree: Ph.D.

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
saberi_amin_200408_phd.pdf 397.7Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record