New rounding techniques for the design and analysis of approximation algorithms
Abstract/Contents
- Abstract
- We study two of the most central classical optimization problems, namely the Traveling Salesman problems and Graph Partitioning problems and develop new approximation algorithms for them. We introduce several new techniques for rounding a fractional solution of a continuous relaxation of these problems into near optimal integral solutions. The two most notable of those are the maximum entropy rounding by sampling method and a novel use of higher eigenvectors of graphs.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2013 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Oveis Gharan, Shayan |
|---|---|
| Associated with | Stanford University, Department of Management Science and Engineering. |
| Primary advisor | Saberi, Amin |
| Thesis advisor | Saberi, Amin |
| Thesis advisor | Diaconis, Persi |
| Thesis advisor | Trevisan, Luca |
| Advisor | Diaconis, Persi |
| Advisor | Trevisan, Luca |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Shayan Oveis Gharan. |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2013. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2013 by Shayan Oveis Gharan
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...