Rounding by sampling
Abstract/Contents
- Abstract
- In this thesis we introduce a new technique for designing approximation algorithms for a class of discrete optimization problems. The idea, that we call "Rounding by Sampling'', is basically a technique for rounding the optimal fractional solution of the problem (obtained from the relaxation of the original problem into a continuous domain) back to the integral domain. The technique is based on sampling from a maximum entropy distribution over the combinatorial structures hidden in the feasible solutions. The main implication of our technique is that it keeps the combinatorial structures intact, while aiming to preserve the solutions quantitatively. We present our technique on combinatorial structures such as spanning trees and matchings. Our results suggest a new approach to attack discrete optimization problems: the path goes through the well-known idea of relaxation the problem into the continuous domain and then finding a (fractional) optimal solution in the relaxed domain using the known techniques of optimization literature, e.g. interior point method, ellipsoid method, etc. After that, our technique comes to help: it enables us to transform the fractional solution back to an integral feasible solution of the original problem, while ensuring that we do not lose much, quantitatively. Using this approach, we show how to design approximation algorithms for two of the most well-known problems in discrete optimization: the traveling salesman problem and the fair allocation of indivisible goods.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2010 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Asadpour Rahimabadi, Arash |
|---|---|
| Associated with | Stanford University, Department of Management Science and Engineering |
| Primary advisor | Saberi, Amin |
| Thesis advisor | Saberi, Amin |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Ye, Yinyu |
| Advisor | Goel, Ashish |
| Advisor | Ye, Yinyu |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Arash Asadpour Rahimabadi. |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering. |
| Thesis | Thesis (Ph. D.)--Stanford University, 2010. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2010 by Arash Asadpour Rahimabadi
- 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...