A computational study of a geometric embedding of minimum multiway cut
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/37070 |
| _version_ | 1811094571299373056 |
|---|---|
| author | Shin, David (David Donghun) |
| author2 | David R. Karger. |
| author_facet | David R. Karger. Shin, David (David Donghun) |
| author_sort | Shin, David (David Donghun) |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. |
| first_indexed | 2024-09-23T16:02:11Z |
| format | Thesis |
| id | mit-1721.1/37070 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:02:11Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/370702019-04-10T09:05:33Z A computational study of a geometric embedding of minimum multiway cut Shin, David (David Donghun) David R. Karger. 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 (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. Includes bibliographical references (p. 77-78). In the minimum multiway cut problem, the goal is to find a minimum cost set of edges whose removal disconnects a certain set of k distinguished vertices in a graph. The problem is MAX-SNP hard for k >/= 3. Clinescu, Karloff, and Rabani gave a geometric relaxation of the problem and a rounding scheme, to produce an approximation algorithm that has a performance guarantee of 3/2 - 1/k. In a subsequent study, Karger, Klein, Stein, Thorup, and Young discovered improved rounding schemes via computation experiments for various values of k, yielding approximation algorithms with improved performance guarantees. Their rounding scheme for k = 3 is provably optimal (i.e., its performance guarantee is equal to the integrality gap of the relaxation), but their rounding schemes for k > 3 seemed unlikely to be optimal. In the present work, we improve these rounding schemes for small values of k > 3, yielding improved approximation algorithms. These improvements were discovered by applying an improved analysis to the same set of computational experiments used by Karger et al. (cont.) We also present computer-aided proofs of improved lower bounds on the integrality gap for various values of k > 3. For the k = 4 case, for instance, our work demonstrates a lower and upper bound of 1.1052 and 1.1494, respectively, improving upon the previously best known bounds of 1.0909 and 1.1539. Finally, we present additional computational experiments that may shed some light on the nature of the optimal rounding scheme for the k = 4 case. by David Shin. M.Eng. 2007-04-03T17:08:25Z 2007-04-03T17:08:25Z 2006 2006 Thesis http://hdl.handle.net/1721.1/37070 83258843 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 78 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Shin, David (David Donghun) A computational study of a geometric embedding of minimum multiway cut |
| title | A computational study of a geometric embedding of minimum multiway cut |
| title_full | A computational study of a geometric embedding of minimum multiway cut |
| title_fullStr | A computational study of a geometric embedding of minimum multiway cut |
| title_full_unstemmed | A computational study of a geometric embedding of minimum multiway cut |
| title_short | A computational study of a geometric embedding of minimum multiway cut |
| title_sort | computational study of a geometric embedding of minimum multiway cut |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/37070 |
| work_keys_str_mv | AT shindaviddaviddonghun acomputationalstudyofageometricembeddingofminimummultiwaycut AT shindaviddaviddonghun computationalstudyofageometricembeddingofminimummultiwaycut |