Abstract
Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is maximized. Although the problem has been extensively studied in the literature, it is surprising that prior to this work, no nontrivial approximation algorithm had been designed and analyzed for its metric case, where the edge weights in the input graph satisfy the triangle inequality. In this paper, we design the first nontrivial polynomial-time approximation algorithm for the maximum-weight metric triangle packing problem. Our algorithm is randomized and achieves an expected approximation ratio of \(0.66768 - \epsilon \) for any constant \(\epsilon > 0\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arkin EM, Hassin R (1998) On local search for weighted packing problems. Math Oper Res 23:640–648
Berman P (2000) A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. In: Proceedings of the 7th scandinavian workshop on algebraic theory (SWAT’00), LNCS 1851, p 214–219,
Chen Z-Z, Tanahashi R, Wang L (2009) An improved randomized approximation algorithm for maximum triangle packing. Discrete Appl Math 157:1640–1646
Chen Z-Z, Tanahashi R, Wang L (2010) Erratum to an improved randomized approximation algorithm for maximum triangle packing. Discrete Appl Math 158:1045–1047
Chlebík M, Chlebíková J (2003) Approximation hardness for small occurrence instances of NP-hard problems. Proc ISAAC 2003:152–164
Cygan M (2013) Improved approximation for \(3\)-dimensional matching via bounded pathwidth local search. Proc FOCS 2013:509–518
Fürer M, Yu H (2014) Approximating the \(k\)-set packing problem by local improvements. Proc ISCO 2014:408–420
Gabow HN (1976) An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. J ACM 23:221–234
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco
Guruswami V, Rangan CP, Chang MS, Chang GJ, Wong CK (1998) The vertex disjoint triangles problem. Proc WG 1998:26–37
Halldórsson MM (1995) Approximating discrete collections via local improvement. In: ACM-SIAM Proceedings of the 6th annual symposium on discrete algorithms (SODA’95), pp 160–169
Hartvigsen D (1984) Extensions of matching theory. PhD thesis, Department of Mathematics, Carnegie-Mellon University
Hassin R, Rubinstein S (2006a) An approximation algorithm for maximum triangle packing. Discrete Appl Math 154:971–979
Hassin R, Rubinstein S (2006b) Erratum to an approximation algorithm for maximum triangle packing. Discrete Appl Math 154:2620
Hurkens CAJ, Schrijver A (1989) 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:68–72
Kann V (1991) Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf Process Lett 37:27–35
Manic G, Wakabayashi Y (2008) Packing triangles in low degree graphs and indifference graphs. Discrete Math 308:1455–1471
van Rooij JMM, van Kooten Niekerk ME, Bodlaender HL (2013) Partition into triangles on bounded degree graphs. Theory Comput Syst 52:687–718
van Zuylen A (2013) Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems. Discrete Appl Math 161:2142–2157
Acknowledgements
YC and AZ are supported by the NSFC Grants 11971139, 11771114 and 11571252; and supported by the CSC Grants 201508330054 and 201908330090, respectively. ZZC is supported by the Grant-in-Aid for Scientific Research of the Ministry of Education, Science, Sports and Culture of Japan, under Grant No. 18K11183. GL is supported by the NSERC Canada. LW is supported by a Grant for Hong Kong Special Administrative Region, China (CityU 11210119).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
An extended abstract appears in the Proceedings of COCOA 2019. LNCS 11949, pages 119–129.
Rights and permissions
About this article
Cite this article
Chen, Y., Chen, ZZ., Lin, G. et al. A randomized approximation algorithm for metric triangle packing. J Comb Optim 41, 12–27 (2021). https://doi.org/10.1007/s10878-020-00660-7
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-020-00660-7