A randomized approximation algorithm for metric triangle packing

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)12–27
Journal / PublicationJournal of Combinatorial Optimization
Volume41
Issue number1
Online published13 Oct 2020
Publication statusPublished - Jan 2021

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.

Research Area(s)

  • Approximation algorithm, Maximum cycle cover, Metric, Randomized algorithm, Triangle packing

Citation Format(s)

A randomized approximation algorithm for metric triangle packing. / Chen, Yong; Chen, Zhi-Zhong; Lin, Guohui; Wang, Lusheng; Zhang, An.

In: Journal of Combinatorial Optimization, Vol. 41, No. 1, 01.2021, p. 12–27.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review