From graphs to matrices, and back : new techniques for graph algorithms
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/66014 |
| _version_ | 1826209784950423552 |
|---|---|
| author | Mądry, Aleksander |
| author2 | Michel X. Goemans and Jonathan A. Kelner. |
| author_facet | Michel X. Goemans and Jonathan A. Kelner. Mądry, Aleksander |
| author_sort | Mądry, Aleksander |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011. |
| first_indexed | 2024-09-23T14:30:13Z |
| format | Thesis |
| id | mit-1721.1/66014 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:30:13Z |
| publishDate | 2011 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/660142019-04-10T23:07:22Z From graphs to matrices, and back : new techniques for graph algorithms New techniques for graph algorithms Mądry, Aleksander Michel X. Goemans and Jonathan A. Kelner. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. 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, 2011. Cataloged from PDF version of thesis. Includes bibliographical references (p. 181-192). The growing need to deal efficiently with massive computing tasks prompts us to consider the following question: How well can we solve fundamental optimization problems if our algorithms have to run really quickly? The motivation for the research presented in this thesis stems from addressing the above question in the context of algorithmic graph theory. To pursue this direction, we develop a toolkit that combines a diverse set of modern algorithmic techniques, including sparsification, low-stretch spanning trees, the multiplicative-weights-update method, dynamic graph algorithms, fast Laplacian system solvers, and tools of spectral graph theory. Using this toolkit, we obtain improved algorithms for several basic graph problems including: -- The Maximum s-t Flow and Minimum s-t Cut Problems. We develop a new approach to computing (1 - [epsilon])-approximately maximum s-t flow and (1 + [epsilon])-approximately minimum s-t cut in undirected graphs that gives the fastest known algorithms for these tasks. These algorithms are the first ones to improve the long-standing bound of O(n3/2') running time on sparse graphs; -- Multicommodity Flow Problems. We set forth a new method of speeding up the existing approximation algorithms for multicommodity flow problems, and use it to obtain the fastest-known (1 - [epsilon])-approximation algorithms for these problems. These results improve upon the best previously known bounds by a factor of roughly [omega](m/n), and make the resulting running times essentially match the [omega](mn) "flow-decomposition barrier" that is a natural obstacle to all the existing approaches; -- " Undirected (Multi-)Cut-Based Minimization Problems. We develop a general framework for designing fast approximation algorithms for (multi-)cutbased minimization problems in undirected graphs. Applying this framework leads to the first algorithms for several fundamental graph partitioning primitives, such as the (generalized) sparsest cut problem and the balanced separator problem, that run in close to linear time while still providing polylogarithmic approximation guarantees; -- The Asymmetric Traveling Salesman Problem. We design an O( )- approximation algorithm for the classical problem of combinatorial optimization: the asymmetric traveling salesman problem. This is the first asymptotic improvement over the long-standing approximation barrier of e(log n) for this problem; -- Random Spanning Tree Generation. We improve the bound on the time needed to generate an uniform random spanning tree of an undirected graph. by Aleksander Mądry. Ph.D. 2011-09-27T18:32:34Z 2011-09-27T18:32:34Z 2011 2011 Thesis http://hdl.handle.net/1721.1/66014 751932691 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 192 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Mądry, Aleksander From graphs to matrices, and back : new techniques for graph algorithms |
| title | From graphs to matrices, and back : new techniques for graph algorithms |
| title_full | From graphs to matrices, and back : new techniques for graph algorithms |
| title_fullStr | From graphs to matrices, and back : new techniques for graph algorithms |
| title_full_unstemmed | From graphs to matrices, and back : new techniques for graph algorithms |
| title_short | From graphs to matrices, and back : new techniques for graph algorithms |
| title_sort | from graphs to matrices and back new techniques for graph algorithms |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/66014 |
| work_keys_str_mv | AT madryaleksander fromgraphstomatricesandbacknewtechniquesforgraphalgorithms AT madryaleksander newtechniquesforgraphalgorithms |