Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các phương pháp gần đúng tốt hơn cho những bài toán tăng cường kết nối và tăng cường cây từ lá tới lá
Springer Science and Business Media LLC - Trang 1-35 - 2023
Tóm tắt
Vấn đề Tăng cường Kết nối (CAP) cùng với một trường hợp đặc biệt nổi tiếng được biết đến là Vấn đề Tăng cường Cây (TAP) là một trong những vấn đề Cấu trúc Mạng cơ bản nhất. Gần đây đã diễn ra một sự bùng nổ trong việc tìm kiếm các thuật toán xấp xỉ với đảm bảo thấp hơn 2 cho cả TAP và CAP, dẫn tới hệ số xấp xỉ tốt nhất hiện nay cho cả hai bài toán là 1.393 thông qua các kỹ thuật khá tinh vi. Chúng tôi trình bày một phương pháp mới dựa trên ghép cặp, có thể được cho là đơn giản, cho trường hợp đặc biệt nổi tiếng của các bài toán từ lá tới lá. Kết hợp công trình của chúng tôi với các kỹ thuật trước đây, chúng tôi dễ dàng có được một xấp xỉ $$(4/3+\varepsilon )$$ cho CAP từ lá tới lá bằng cách trả về phương án tốt nhất giữa phương án của chúng tôi và một trong những phương pháp hiện có. Trước công trình của chúng tôi, một đảm bảo $$4/3$$ chỉ được biết đến cho các trường hợp TAP từ lá tới lá trên các cây có độ cao 2. Hơn nữa, khi kết hợp kỹ thuật của chúng tôi với một phương pháp phân tích ngăn xếp được giới thiệu gần đây, là một phần trong xấp xỉ 1.393 đã đề cập ở trên, chúng tôi có thể cải thiện thêm hệ số xấp xỉ xuống còn 1.29, đạt được lần đầu tiên một hệ số dưới $$\frac{4}{3}$$ cho một lớp bài toán TAP/CAP không tầm thường.
Từ khóa
#Tăng cường Kết nối #Tăng cường Cây #Thuật toán xấp xỉ #Vấn đề từ lá tới lá #Ghép cặpTài liệu tham khảo
Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Trans. Algorithms 15(2), 19:1-19:26 (2018)
Basavaraju, M., Fomin, F.V., Golovach, P., Misra, P., Ramanujan, M.S., Saurabh, S.: Parameterized algorithms to preserve connectivity. In: Proceedings of 41st International Colloquium on Automata, Languages, and Programming (ICALP), pp. 800–811 (2014)
Cecchetto, F., Traub, V., Zenklusen, R.: Bridging the gap between tree and connectivity augmentation: Unified and stronger approaches. https://arxiv.org/abs/2012.00086v3 (2020). A short version appeared in the proceedings of STOC 2021
Cheriyan, J., Gao, Z.: Approximating (unweighted) tree augmentation via lift-and-project, part II. Algorithmica 80(2), 608–651 (2018). https://doi.org/10.1007/s00453-017-0275-7
Cheriyan, J., Gao, Z.: Approximating (unweighted) tree augmentation via lift-and-project, part I: stemless TAP. Algorithmica 80(2), 530–559 (2018)
Cheriyan, J., Jordán, T., Ravi, R.: On 2-coverings and 2-packings of laminar families. In: Proceedings of 7th Annual European Symposium on Algorithms (ESA), pp. 510–520 (1999)
Cheriyan, J., Karloff, H., Khandekar, R., Könemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4), 399–401 (2008)
Cohen, N., Nutov, Z.: A \((1+ \ln 2)\)-approximation algorithm for minimum-cost \(2\)-edge-connectivity augmentation of trees with constant radius. Theor. Comput. Sci. 489, 67–74 (2013)
Dinitz, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of the system of minimum edge cuts of a graph. Studies in Discrete Optimization, pp. 290–306 (1976)
Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A \(1.8\) approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\). ACM Trans. Algorithms 5(2), 21:1-21:17 (2009)
Fiorini, S., Groß, M., Könemann, J., Sanità, L.: Approximating weighted tree augmentation via Chvátal-Gomory Cuts. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 817–831 (2018)
Frank, A.: Rooted k-connections in digraphs. Discret. Appl. Math. 157(6), 1242–1254 (2009). https://doi.org/10.1016/j.dam.2008.03.040
Frederickson, G.N., JáJá, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2), 270–283 (1981)
Garg, M., Grandoni, F., Jabal Ameli, A.: Improved approximation for two-edge-connectivity (2022). arxiv:2209.10265v2
Goemans, M.X., Goldberg, A.V., Plotkin, S., Shmoys, D.B., Tardos, E., Williamson, D.P.: Improved approximation algorithms for network design problems. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 223–232 (1994)
Grandoni, F., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: saving by rewiring. In: Proceedings of 50th ACM Symposium on Theory of Computing (STOC), pp. 632–645 (2018)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, 2nd corrected edn. Springer (1993)
Iglesias, J., Ravi, R.: Coloring down: \(3/2\)-approximation for special cases of the weighted tree augmentation problem. arxiv:1707.05240 (2018)
Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 39–60 (2001)
Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. J. Algorithms 14(2), 214–225 (1993)
Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput. 33(3), 704–720 (2004)
Kortsarz, G., Nutov, Z.: A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\). ACM Trans. Algorithms 12(2), 23:1-23:20 (2016)
Kortsarz, G., Nutov, Z.: LP-relaxations for tree augmentation. Discret. Appl. Math. 239, 94–105 (2018)
Maduel, Y., Nutov, Z.: Covering a laminar family by leaf to leaf links. Discret. Appl. Math. 158, 1424–1432 (2010)
Nagamochi, H.: An approximation for finding a smallest \(2\)-edge-connected subgraph containing a specified spanning tree. Discret. Appl. Math. 126(1), 83–113 (2003)
Nutov, Z.: On the tree augmentation problem. Algorithmica 83(2), 553–575 (2020). https://doi.org/10.1007/s00453-020-00765-9
Nutov, Z.: Approximation algorithms for connectivity augmentation problems. In: Proceedings of the 16th International Computer Science Symposium in Russia (CSR), pp. 321–338 (2021)