A randomized approximation algorithm for metric triangle packing
- PDF / 444,998 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 250 Views
A randomized approximation algorithm for metric triangle packing Yong Chen1 · Zhi-Zhong Chen2 · Guohui Lin3
· Lusheng Wang4 · An Zhang1
Accepted: 7 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 − for any constant > 0. Keywords Triangle packing · Metric · Approximation algorithm · Randomized algorithm · Maximum cycle cover
An extended abstract appears in the Proceedings of COCOA 2019. LNCS 11949, pages 119–129.
B B
Zhi-Zhong Chen [email protected] Guohui Lin [email protected] Yong Chen [email protected] ; [email protected] Lusheng Wang [email protected]
1
Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
2
Division of Information System Design, Tokyo Denki University, Saitama, Japan
3
Department of Computing Science, University of Alberta, Edmonton, AB T6G 2E8, Canada
4
Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China
123
Journal of Combinatorial Optimization
1 Introduction An instance of the maximum-weight triangle packing problem (MWTP for short) is an edge-weighted complete graph G on 3n vertices, where n is a positive integer. Given G, the objective of MWTP is to compute n vertex-disjoint triangles (a.k.a. cycles of length 3) such that the total weight of edges in these n triangles is maximized. The unweighted (i.e., edge uniformly weighted) variant (MTP for short) is to compute the maximum number of vertex-disjoint triangles in the input graph, which is an edge-unweighted but incomplete graph. In their classic book, (Garey and Johnson 1979, GT11) show that MTP (in fact, a special case called partition into triangles) is NP-hard. Kann (1991) and van Rooij et al. (2013) show that MTP is APX-hard even restricted on graphs of maximum degree 4. Chlebík and Chlebíková (2003) show that unless P = NP, no polynomialtime approximation algorithm for MTP can achieve an approximation ratio of 0.9929. Moreover, Guruswami et al. (1998) show that MTP remains NP-hard even restricted on chordal, planar, line, or total graphs. MTP can be easily cast as a special case of the unweighted 3-set packing problem (U3SP for short). Recall that an instance of U3SP is a family F of sets each of size at most 3 and the objective is to compute a maximum-sized family of disjoint sets in F. On
Data Loading...
