A randomized approximation algorithm for metric triangle packing
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 12–27 |
| Journal / Publication | Journal of Combinatorial Optimization |
| Volume | 41 |
| Issue number | 1 |
| Online published | 13 Oct 2020 |
| Publication status | Published - Jan 2021 |
Link(s)
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 journal › peer-review
