An Improved Approximation Algorithm for Metric Triangle Packing
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916123332575232 |
|---|---|
| author | Zhao, Jingyang Xiao, Mingyu |
| author_facet | Zhao, Jingyang Xiao, Mingyu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08216 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Improved Approximation Algorithm for Metric Triangle Packing Zhao, Jingyang Xiao, Mingyu Data Structures and Algorithms 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. |
| title | An Improved Approximation Algorithm for Metric Triangle Packing |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.08216 |