A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O(logn (logl...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115309 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1811070470288572416 |
|---|---|
| author | Bateni, MohammadHossein Hajiaghayi, MohammadTaghi Marx, Dániel Demaine, Erik D |
| 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 Bateni, MohammadHossein Hajiaghayi, MohammadTaghi Marx, Dániel Demaine, Erik D |
| author_sort | Bateni, MohammadHossein |
| collection | MIT |
| description | We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O(logn (loglogn)O(1)). We achieve this result via a novel and powerful technique called spanner bootstrapping, which allows one to bootstrap from a superconstant approximation factor (even superpolynomial in the input size) all the way down to a PTAS. This is in contrast with the popular existing approach for planar PTASs of constructing light-weight spanners in one iteration, which notably requires a constant-factor approximate solution to start from. Spanner bootstrapping removes one of the main barriers for designing PTASs for problems which have no known constant-factor approximation (even on planar graphs), and thus can be used to obtain PTASs for several difficult-to-approximate problems.
Our second major contribution required for the planar group Steiner tree PTAS is a spanner construction, which reduces the graph to have total weight within a factor of the optimal solution while approximately preserving the optimal solution. This is particularly challenging because group Steiner tree requires deciding which terminal in each group to connect by the tree, making it much harder than recent previous approaches to construct spanners for planar TSP by Klein [SIAM J. Computing 2008], subset TSP by Klein [STOC 2006], Steiner tree by Borradaile, Klein, and Mathieu [ACM Trans. Algorithms 2009], and Steiner forest by Bateni, Hajiaghayi, and Marx [J. ACM 2011] (and its improvement to an efficient PTAS by Eisenstat, Klein, and Mathieu [SODA 2012]. The main conceptual contribution here is realizing that selecting which terminals may be relevant is essentially a complicated prize-collecting process: we have to carefully weigh the cost and benefits of reaching or avoiding certain terminals in the spanner. Via a sequence of involved prize-collecting procedures, we can construct a spanner that reaches a set of terminals that is sufficient for an almost-optimal solution.
Our PTAS for planar group Steiner tree implies the first PTAS for geometric Euclidean group Steiner tree with obstacles, as well as a (2+)-approximation algorithm for group TSP with obstacles, improving over the best previous constant-factor approximation algorithms. By contrast, we show that planar group Steiner forest, a slight generalization of planar group Steiner tree, is APX-hard on planar graphs of treewidth 3, even if the groups are pairwise disjoint and every group is a vertex or an edge. |
| first_indexed | 2024-09-23T08:36:32Z |
| format | Article |
| id | mit-1721.1/115309 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:36:32Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1153092022-09-30T09:56:52Z A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting Bateni, MohammadHossein Hajiaghayi, MohammadTaghi Marx, Dániel Demaine, Erik D Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O(logn (loglogn)O(1)). We achieve this result via a novel and powerful technique called spanner bootstrapping, which allows one to bootstrap from a superconstant approximation factor (even superpolynomial in the input size) all the way down to a PTAS. This is in contrast with the popular existing approach for planar PTASs of constructing light-weight spanners in one iteration, which notably requires a constant-factor approximate solution to start from. Spanner bootstrapping removes one of the main barriers for designing PTASs for problems which have no known constant-factor approximation (even on planar graphs), and thus can be used to obtain PTASs for several difficult-to-approximate problems. Our second major contribution required for the planar group Steiner tree PTAS is a spanner construction, which reduces the graph to have total weight within a factor of the optimal solution while approximately preserving the optimal solution. This is particularly challenging because group Steiner tree requires deciding which terminal in each group to connect by the tree, making it much harder than recent previous approaches to construct spanners for planar TSP by Klein [SIAM J. Computing 2008], subset TSP by Klein [STOC 2006], Steiner tree by Borradaile, Klein, and Mathieu [ACM Trans. Algorithms 2009], and Steiner forest by Bateni, Hajiaghayi, and Marx [J. ACM 2011] (and its improvement to an efficient PTAS by Eisenstat, Klein, and Mathieu [SODA 2012]. The main conceptual contribution here is realizing that selecting which terminals may be relevant is essentially a complicated prize-collecting process: we have to carefully weigh the cost and benefits of reaching or avoiding certain terminals in the spanner. Via a sequence of involved prize-collecting procedures, we can construct a spanner that reaches a set of terminals that is sufficient for an almost-optimal solution. Our PTAS for planar group Steiner tree implies the first PTAS for geometric Euclidean group Steiner tree with obstacles, as well as a (2+)-approximation algorithm for group TSP with obstacles, improving over the best previous constant-factor approximation algorithms. By contrast, we show that planar group Steiner forest, a slight generalization of planar group Steiner tree, is APX-hard on planar graphs of treewidth 3, even if the groups are pairwise disjoint and every group is a vertex or an edge. National Science Foundation (U.S.) (Grant CCF-1161626) National Science Foundation (U.S.) (Grant IIS-1546108) United States. Air Force. Office of Scientific Research (GRAPHS Grant FA9550- 12-1-0423) 2018-05-11T13:50:44Z 2018-05-11T13:50:44Z 2016-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-4132-5 http://hdl.handle.net/1721.1/115309 Bateni, MohammadHossein, et al. "A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting." STOC '16 Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 19-21 June, 2016, Cambridge, Massachusetts, ACM Press, 2016, pp. 570–83. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1145/2897518.2897549 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) Other univ. web domain |
| spellingShingle | Bateni, MohammadHossein Hajiaghayi, MohammadTaghi Marx, Dániel Demaine, Erik D A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting |
| title | A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting |
| title_full | A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting |
| title_fullStr | A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting |
| title_full_unstemmed | A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting |
| title_short | A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting |
| title_sort | ptas for planar group steiner tree via spanner bootstrapping and prize collecting |
| url | http://hdl.handle.net/1721.1/115309 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT batenimohammadhossein aptasforplanargroupsteinertreeviaspannerbootstrappingandprizecollecting AT hajiaghayimohammadtaghi aptasforplanargroupsteinertreeviaspannerbootstrappingandprizecollecting AT marxdaniel aptasforplanargroupsteinertreeviaspannerbootstrappingandprizecollecting AT demaineerikd aptasforplanargroupsteinertreeviaspannerbootstrappingandprizecollecting AT batenimohammadhossein ptasforplanargroupsteinertreeviaspannerbootstrappingandprizecollecting AT hajiaghayimohammadtaghi ptasforplanargroupsteinertreeviaspannerbootstrappingandprizecollecting AT marxdaniel ptasforplanargroupsteinertreeviaspannerbootstrappingandprizecollecting AT demaineerikd ptasforplanargroupsteinertreeviaspannerbootstrappingandprizecollecting |