A deterministic approximation algorithm for metric triangle packing. (English) Zbl 07898961
Summary: Given an edge-weighted metric complete graph with \(n\) vertices, the maximum weight metric triangle packing problem is to find a set of \(n / 3\) vertex-disjoint triangles with the total weight of all triangles in the packing maximized. Several simple methods can lead to a 2/3-approximation ratio. However, this barrier is not easy to break. Chen et al. proposed a randomized approximation algorithm with an expected ratio of \((0.66768 - \varepsilon)\) for any constant \(\varepsilon > 0\). In this paper, we improve the approximation ratio to \((0.66835 - \varepsilon)\). Furthermore, we can derandomize our algorithm.
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Kirkpatrick, D. G.; Hell, P., On the completeness of a generalized matching problem, (STOC 1978, 1978, ACM), 240-245 · Zbl 1282.68182 |
| [2] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, W. H. Freeman · Zbl 0411.68039 |
| [3] | Guruswami, V.; Rangan, C. P.; Chang, M.; Chang, G. J.; Wong, C. K., The vertex-disjoint triangles problem, (WG 1998, vol. 1517, 1998), 26-37 · Zbl 0918.68081 |
| [4] | Kann, V., Maximum bounded 3-dimensional matching is MAX snp-complete, Inf. Process. Lett., 37, 1, 27-35, 1991 · Zbl 0711.68045 |
| [5] | van Rooij, J. M.M.; van Kooten Niekerk, M. E.; Bodlaender, H. L., Partition into triangles on bounded degree graphs, Theory Comput. Syst., 52, 4, 687-718, 2013 · Zbl 1286.68214 |
| [6] | Chlebík, M.; Chlebíková, J., Approximation hardness for small occurrence instances of NP-Hard problems, (CIAC 2003, vol. 2653, 2003), 152-164 · Zbl 1032.68082 |
| [7] | Hurkens, C. A.J.; Schrijver, A., On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math., 2, 1, 68-72, 1989 · Zbl 0733.05003 |
| [8] | Halldórsson, M. M., Approximating discrete collections via local improvements, (SODA 1995, 1995, ACM/SIAM), 160-169 · Zbl 0847.90136 |
| [9] | Cygan, M., Improved approximation for 3-dimensional matching via bounded pathwidth local search, (FOCS 2013, 2013, IEEE Computer Society), 509-518 |
| [10] | Fürer, M.; Yu, H., Approximating the k-set packing problem by local improvements, (ISCO 2014, vol. 8596, 2014), 408-420 · Zbl 1452.90264 |
| [11] | Manic, G.; Wakabayashi, Y., Packing triangles in low degree graphs and indifference graphs, Discrete Math., 308, 8, 1455-1471, 2008 · Zbl 1136.05073 |
| [12] | Arkin, E. M.; Hassin, R., On local search for weighted k-set packing, Math. Oper. Res., 23, 3, 640-648, 1998 · Zbl 0977.90038 |
| [13] | Berman, P., A \(d / 2\) approximation for maximum weight independent set in d-claw free graphs, Nord. J. Comput., 7, 3, 178-184, 2000 · Zbl 0972.68127 |
| [14] | Neuwohner, M., An improved approximation algorithm for the maximum weight independent set problem in d-claw free graphs, (STACS 2021. STACS 2021, LIPIcs, vol. 187, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 53:1-53:20 |
| [15] | Thiery, T.; Ward, J., An improved approximation for maximum weighted k-set packing, (SODA 2023, 2023, SIAM), 1138-1162 · Zbl 07848002 |
| [16] | Hassin, R.; Rubinstein, S., An approximation algorithm for maximum triangle packing, Discrete Appl. Math., 154, 6, 971-979, 2006 · Zbl 1101.68983 |
| [17] | Hassin, R.; Rubinstein, S., Erratum to “An approximation algorithm for maximum triangle packing” [Discrete Applied Mathematics 154 (2006) 971-979], Discrete Appl. Math., 154, 18, 2620, 2006 · Zbl 1101.68983 |
| [18] | Chen, Z.; Tanahashi, R.; Wang, L., An improved randomized approximation algorithm for maximum triangle packing, Discrete Appl. Math., 157, 7, 1640-1646, 2009 · Zbl 1172.68681 |
| [19] | Chen, Z.; Tanahashi, R.; Wang, L., Erratum to “An improved randomized approximation algorithm for maximum triangle packing” [Discrete Appl. Math. 157 (2009) 1640-1646], Discrete Appl. Math., 158, 9, 1045-1047, 2010 · Zbl 1255.68300 |
| [20] | van Zuylen, A., Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems, Discrete Appl. Math., 161, 13-14, 2142-2157, 2013 · Zbl 1293.90064 |
| [21] | Bar-Noy, A.; Peleg, D.; Rabanca, G.; Vigan, I., Improved approximation algorithms for weighted 2-path partitions, Discrete Appl. Math., 239, 15-37, 2018 · Zbl 1382.05056 |
| [22] | Hassin, R.; Rubinstein, S.; Tamir, A., Approximation algorithms for maximum dispersion, Oper. Res. Lett., 21, 3, 133-137, 1997 · Zbl 0888.90144 |
| [23] | Chen, Y.; Chen, Z.; Lin, G.; Wang, L.; Zhang, A., A randomized approximation algorithm for metric triangle packing, J. Comb. Optim., 41, 1, 12-27, 2021 · Zbl 1468.90103 |
| [24] | Zhao, J.; Xiao, M., An improved approximation algorithm for metric triangle packing, (Chen, X.; Li, B., Theory and Applications of Models of Computation - 18th Annual Conference, TAMC 2024, Hong Kong, China, May 13-15, 2024, Proceedings. Theory and Applications of Models of Computation - 18th Annual Conference, TAMC 2024, Hong Kong, China, May 13-15, 2024, Proceedings, Lecture Notes in Computer Science, vol. 14637, 2024, Springer), 50-62 |
| [25] | Gabow, H. N., Implementation of algorithms for maximum matching on nonbipartite graphs, 1974, Stanford University, Ph.D. thesis |
| [26] | Lawler, E., Combinatorial Optimization: Networks and Matroids, 1976, Holt, Rinehart and Winston · Zbl 0413.90040 |
| [27] | Hartvigsen, D., Extensions of matching theory, 1984, Carnegie-Mellon University, Ph.D. thesis |
| [28] | Williamson, D. P.; Shmoys, D. B., The Design of Approximation Algorithms, 2011, Cambridge University Press · Zbl 1219.90004 |
| [29] | Li, S.; Yu, W., Approximation algorithms for the maximum-weight cycle/path packing problems, Asia-Pac. J. Oper. Res., 40, 4, 2340003:1-2340003:16, 2023 · Zbl 07852410 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
