New rounding techniques for the design and analysis of approximation algorithms
- 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.
|Type of resource
|electronic; electronic resource; remote
|1 online resource.
|Oveis Gharan, Shayan
|Stanford University, Department of Management Science and Engineering.
|Statement of responsibility
|Shayan Oveis Gharan.
|Submitted to the Department of Management Science and Engineering.
|Thesis (Ph.D.)--Stanford University, 2013.
- © 2013 by Shayan Oveis Gharan
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...