A Randomized Approximation Algorithm for Metric Triangle Packing

Yong Chen; Zhi-Zhong Chen; Guohui Lin; Lusheng Wang; An Zhang

doi:10.1007/978-3-030-36412-0_10

A Randomized Approximation Algorithm for Metric Triangle Packing

Yong Chen, Zhi-Zhong Chen^*, Guohui Lin^*, Lusheng Wang, An Zhang

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem (MWTP for short) 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 MWTP 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 (denoted by MMWTP), 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 MMWTP. Our algorithm is randomized and achieves an expected approximation ratio of 0.66745 − ε for any constant ε > 0.

Original language	English
Title of host publication	Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings
Editors	Yingshu Li, Mihaela Cardei, Yan Huang
Publisher	Springer
Pages	119-129
ISBN (Electronic)	9783030364120
ISBN (Print)	9783030364113
DOIs	https://doi.org/10.1007/978-3-030-36412-0_10
Publication status	Published - Dec 2019
Event	13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019) - Xiamen, China Duration: 13 Dec 2019 → 15 Dec 2019

Publication series

Name	Lecture Notes in Computer Science
Volume	11949
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019)
Place	China
City	Xiamen
Period	13/12/19 → 15/12/19

Research Keywords

Approximation algorithm
Maximum cycle cover
Metric
Randomized algorithm
Triangle packing

Access Output

10.1007/978-3-030-36412-0_10

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, Y., Chen, Z.-Z., Lin, G., Wang, L., & Zhang, A. (2019). A Randomized Approximation Algorithm for Metric Triangle Packing. In Y. Li, M. Cardei, & Y. Huang (Eds.), Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings (pp. 119-129). (Lecture Notes in Computer Science; Vol. 11949). Springer . https://doi.org/10.1007/978-3-030-36412-0_10

@inproceedings{34ec8aec05384121930162444fd21857,

title = "A Randomized Approximation Algorithm for Metric Triangle Packing",

abstract = "Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem (MWTP for short) 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 MWTP 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 (denoted by MMWTP), 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 MMWTP. Our algorithm is randomized and achieves an expected approximation ratio of 0.66745 − ε for any constant ε > 0.",

keywords = "Approximation algorithm, Maximum cycle cover, Metric, Randomized algorithm, Triangle packing",

author = "Yong Chen and Zhi-Zhong Chen and Guohui Lin and Lusheng Wang and An Zhang",

year = "2019",

month = dec,

doi = "10.1007/978-3-030-36412-0_10",

language = "English",

isbn = "9783030364113",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "119--129",

editor = "Yingshu Li and Mihaela Cardei and Yan Huang",

booktitle = "Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings",

note = "13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019) ; Conference date: 13-12-2019 Through 15-12-2019",

}

Chen, Y, Chen, Z-Z, Lin, G, Wang, L & Zhang, A 2019, A Randomized Approximation Algorithm for Metric Triangle Packing. in Y Li, M Cardei & Y Huang (eds), Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings. Lecture Notes in Computer Science, vol. 11949, Springer , pp. 119-129, 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), Xiamen, China, 13/12/19. https://doi.org/10.1007/978-3-030-36412-0_10

A Randomized Approximation Algorithm for Metric Triangle Packing. / Chen, Yong; Chen, Zhi-Zhong; Lin, Guohui et al.
Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings. ed. / Yingshu Li; Mihaela Cardei; Yan Huang. Springer , 2019. p. 119-129 (Lecture Notes in Computer Science; Vol. 11949).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A Randomized Approximation Algorithm for Metric Triangle Packing

AU - Chen, Yong

AU - Chen, Zhi-Zhong

AU - Lin, Guohui

AU - Wang, Lusheng

AU - Zhang, An

PY - 2019/12

Y1 - 2019/12

N2 - Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem (MWTP for short) 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 MWTP 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 (denoted by MMWTP), 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 MMWTP. Our algorithm is randomized and achieves an expected approximation ratio of 0.66745 − ε for any constant ε > 0.

AB - Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem (MWTP for short) 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 MWTP 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 (denoted by MMWTP), 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 MMWTP. Our algorithm is randomized and achieves an expected approximation ratio of 0.66745 − ε for any constant ε > 0.

KW - Approximation algorithm

KW - Maximum cycle cover

KW - Metric

KW - Randomized algorithm

KW - Triangle packing

UR - http://www.scopus.com/inward/record.url?scp=85078519220&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85078519220&origin=recordpage

U2 - 10.1007/978-3-030-36412-0_10

DO - 10.1007/978-3-030-36412-0_10

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783030364113

T3 - Lecture Notes in Computer Science

SP - 119

EP - 129

BT - Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings

A2 - Li, Yingshu

A2 - Cardei, Mihaela

A2 - Huang, Yan

PB - Springer

T2 - 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019)

Y2 - 13 December 2019 through 15 December 2019

ER -

A Randomized Approximation Algorithm for Metric Triangle Packing

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this