Show simple item record

dc.contributor.authorSaberi, Aminen_US
dc.date.accessioned2005-06-16T20:22:35Z
dc.date.available2005-06-16T20:22:35Z
dc.date.issued2004-07-12en_US
dc.identifier.urihttp://hdl.handle.net/1853/6427
dc.description.abstractThe 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.en_US
dc.format.extent407275 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectInterneten_US
dc.subjectAlgorithmsen_US
dc.subjectGame theoryen_US
dc.subject.lcshInternet programmingen_US
dc.subject.lcshGame theoryen_US
dc.subject.lcshComputer networks Scalabilityen_US
dc.subject.lcshAlgorithmsen_US
dc.titleAlgorithmic Aspects of the Interneten_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentAlgorithms, Combinatorics, and Optimizationen_US
dc.contributor.departmentComputing
dc.description.advisorCommittee Co-Chairs: Milena Mihail ; Vijay Vazirani ; Committee Members: Yan Ding ; Richard Duke ; Dana Randallen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record