Optimization problems in network connectivity
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/78362 |
| _version_ | 1826199458478555136 |
|---|---|
| author | Panigrahi, Debmalya |
| author2 | David R. Karger. |
| author_facet | David R. Karger. Panigrahi, Debmalya |
| author_sort | Panigrahi, Debmalya |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012. |
| first_indexed | 2024-09-23T11:20:13Z |
| format | Thesis |
| id | mit-1721.1/78362 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:20:13Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/783622019-04-11T00:17:26Z Optimization problems in network connectivity Panigrahi, Debmalya David R. Karger. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (p. 115-120). Besides being one of the principal driving forces behind research in algorithmic theory for more than five decades, network optimization has assumed increased significance in recent times with the advent and widespread use of a variety of large-scale real-life networks. The primary goal of such networks is to connect vertices (representing a variety of real-life entities) in a robust and inexpensive manner, and to store and retrieve such connectivity information efficiently. In this thesis, we present efficient algorithms aimed at achieving these broad goals. The main results presented in this thesis are as follows. -- Cactus Construction. We give a near-linear time Monte Carlo algorithm for constructing a cactus representation of all the minimum cuts in an undirected graph. -- Cut Sparsification. A cut sparsifier of an undirected graph is a sparse graph on the same set of vertices that preserves its cut values up to small errors. We give new combinatorial and algorithmic results for constructing cut sparsifiers. -- Online Steiner Tree. Given an undirected graph as input, the goal of the Steiner tree problem is to select its minimum cost subgraph that connects a designated subset of vertices. We give the first online algorithm for the Steiner tree problem that has a poly-logarithmic competitive ratio when the input graph has both node and edge costs. -- Network Activation Problems. In the design of real-life wireless networks, a typical objective is to select one among a possible set of parameter values at each node such that the set of activated links satisfy some desired connectivity properties. We formalize this as the network activation model, and give approximation algorithms for various fundamental network design problems in this model. by Debmalya Panigrahi. Ph.D. 2013-04-12T15:14:09Z 2013-04-12T15:14:09Z 2012 2012 Thesis http://hdl.handle.net/1721.1/78362 832728876 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 120 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Panigrahi, Debmalya Optimization problems in network connectivity |
| title | Optimization problems in network connectivity |
| title_full | Optimization problems in network connectivity |
| title_fullStr | Optimization problems in network connectivity |
| title_full_unstemmed | Optimization problems in network connectivity |
| title_short | Optimization problems in network connectivity |
| title_sort | optimization problems in network connectivity |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/78362 |
| work_keys_str_mv | AT panigrahidebmalya optimizationproblemsinnetworkconnectivity |