Approximation Algorithms via Contraction Decomposition
http://www.springerlink.com/content/h96773m010737357/fulltext.pdf
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Bolyai Society/Springer-Verlag
2011
|
| Online Access: | http://hdl.handle.net/1721.1/63808 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826213176184668160 |
|---|---|
| author | Hajiaghayi, Mohammad Taghi Demaine, Erik D. Mohar, Bojan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Hajiaghayi, Mohammad Taghi Demaine, Erik D. Mohar, Bojan |
| author_sort | Hajiaghayi, Mohammad Taghi |
| collection | MIT |
| description | http://www.springerlink.com/content/h96773m010737357/fulltext.pdf |
| first_indexed | 2024-09-23T15:44:32Z |
| format | Article |
| id | mit-1721.1/63808 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:44:32Z |
| publishDate | 2011 |
| publisher | Bolyai Society/Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/638082022-10-02T03:48:57Z Approximation Algorithms via Contraction Decomposition Hajiaghayi, Mohammad Taghi Demaine, Erik D. Mohar, Bojan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Erik D. http://www.springerlink.com/content/h96773m010737357/fulltext.pdf We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained in [Bak94, Epp00, DDO+04, DHK05], and it generalizes a similar result for \compression" (a variant of contraction) in planar graphs [Kle05]. Our decomposition result is a powerful tool for obtaining PTASs for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. We prove that any contraction-closed problem satisfying just a few simple conditions has a PTAS in bounded-genus graphs. In particular, our framework yields PTASs for the weighted Traveling Salesman Problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing previous algorithms of [GKP95, AGK+98, Kle05, Gri00, CGSZ04, BCGZ05]. We also highlight the only main di culty in extending our results to general H-minor-free graphs. 2011-06-09T18:24:01Z 2011-06-09T18:24:01Z 2010-09 2006-09 Article http://purl.org/eprint/type/JournalArticle 0209-9683 http://hdl.handle.net/1721.1/63808 Demaine, Erik, MohammadTaghi Hajiaghayi and Bojan Mohar. “Approximation Algorithms via Contraction Decomposition.” Combinatorica 30.5 (2010) : 533-552. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/s00493-010-2341-5 Combinatorica Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Bolyai Society/Springer-Verlag MIT web domain |
| spellingShingle | Hajiaghayi, Mohammad Taghi Demaine, Erik D. Mohar, Bojan Approximation Algorithms via Contraction Decomposition |
| title | Approximation Algorithms via Contraction Decomposition |
| title_full | Approximation Algorithms via Contraction Decomposition |
| title_fullStr | Approximation Algorithms via Contraction Decomposition |
| title_full_unstemmed | Approximation Algorithms via Contraction Decomposition |
| title_short | Approximation Algorithms via Contraction Decomposition |
| title_sort | approximation algorithms via contraction decomposition |
| url | http://hdl.handle.net/1721.1/63808 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT hajiaghayimohammadtaghi approximationalgorithmsviacontractiondecomposition AT demaineerikd approximationalgorithmsviacontractiondecomposition AT moharbojan approximationalgorithmsviacontractiondecomposition |