# A Randomized Approximation Algorithm for Metric Triangle Packing

Ontology type: schema:Chapter

### Chapter Info

DATE

2019-11-23

AUTHORS 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0.66745 - \epsilon$$\end{document} for any constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon > 0$$\end{document}. More... »

PAGES

119-129

### Book

TITLE

Combinatorial Optimization and Applications

ISBN

978-3-030-36411-3
978-3-030-36412-0

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-36412-0_10

DOI

http://dx.doi.org/10.1007/978-3-030-36412-0_10

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1123154522

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China",
"id": "http://www.grid.ac/institutes/grid.411963.8",
"name": [
"Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Yong",
"id": "sg:person.010555136403.19",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Division of Information System Design, Tokyo Denki University, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, Saitama, Japan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Zhi-Zhong",
"id": "sg:person.015654265661.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computing Science, University of Alberta, Edmonton, Canada",
"id": "http://www.grid.ac/institutes/grid.17089.37",
"name": [
"Department of Computing Science, University of Alberta, Edmonton, Canada"
],
"type": "Organization"
},
"familyName": "Lin",
"givenName": "Guohui",
"id": "sg:person.01130357621.02",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR"
],
"type": "Organization"
},
"familyName": "Wang",
"givenName": "Lusheng",
"id": "sg:person.01105113721.52",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China",
"id": "http://www.grid.ac/institutes/grid.411963.8",
"name": [
"Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China"
],
"type": "Organization"
},
"familyName": "Zhang",
"givenName": "An",
"id": "sg:person.015273653637.29",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015273653637.29"
],
"type": "Person"
}
],
"datePublished": "2019-11-23",
"datePublishedReg": "2019-11-23",
"description": "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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$0.66745 - \\epsilon$$\\end{document} for any constant \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\epsilon > 0$$\\end{document}.",
"editor": [
{
"familyName": "Li",
"givenName": "Yingshu",
"type": "Person"
},
{
"familyName": "Cardei",
"givenName": "Mihaela",
"type": "Person"
},
{
"familyName": "Huang",
"givenName": "Yan",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-030-36412-0_10",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-030-36411-3",
"978-3-030-36412-0"
],
"name": "Combinatorial Optimization and Applications",
"type": "Book"
},
"keywords": [
"approximation algorithm",
"triangle packing problem",
"metric case",
"polynomial-time approximation algorithm",
"expected approximation ratio",
"randomized approximation algorithm",
"graph G",
"packing problem",
"vertex-disjoint triangles",
"nontrivial approximation algorithm",
"input graph",
"triangle inequality",
"approximation ratio",
"triangle packing",
"complete graph G",
"n triangles",
"algorithm",
"vertices",
"problem",
"triangle",
"edge",
"graph",
"inequality",
"total weight",
"literature",
"work",
"cases",
"ratio",
"packing",
"collection",
"weight",
"MWTP",
"paper"
],
"name": "A Randomized Approximation Algorithm for Metric Triangle Packing",
"pagination": "119-129",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1123154522"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-030-36412-0_10"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-030-36412-0_10",
"https://app.dimensions.ai/details/publication/pub.1123154522"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:49",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_91.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-030-36412-0_10"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36412-0_10'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36412-0_10'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36412-0_10'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36412-0_10'

This table displays all metadata directly associated to this object as RDF triples.

140 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0103
3 schema:author N9b12b979989045419540d87e794e1f74
4 schema:datePublished 2019-11-23
5 schema:datePublishedReg 2019-11-23
6 schema:description 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0.66745 - \epsilon$$\end{document} for any constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon > 0$$\end{document}.
7 schema:editor N1a05fc8afdc748878ee67508f2624ee8
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N19a95dc83cae484b9f30d3d9de0ae7d0
12 schema:keywords MWTP
13 algorithm
14 approximation algorithm
15 approximation ratio
16 cases
17 collection
18 complete graph G
19 edge
20 expected approximation ratio
21 graph
22 graph G
23 inequality
24 input graph
25 literature
26 metric case
27 n triangles
28 nontrivial approximation algorithm
29 packing
30 packing problem
31 paper
32 polynomial-time approximation algorithm
33 problem
34 randomized approximation algorithm
35 ratio
36 total weight
37 triangle
38 triangle inequality
39 triangle packing
40 triangle packing problem
41 vertex-disjoint triangles
42 vertices
43 weight
44 work
45 schema:name A Randomized Approximation Algorithm for Metric Triangle Packing
46 schema:pagination 119-129
47 schema:productId N24ccbf71caed43e1b753eea82e89e1d0
49 schema:publisher Na9492b244ae94d92b288e9f54bd269c7
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1123154522
51 https://doi.org/10.1007/978-3-030-36412-0_10
52 schema:sdDatePublished 2022-05-20T07:49
54 schema:sdPublisher N5cc70ee04ea74f0b910da58b08cc408a
55 schema:url https://doi.org/10.1007/978-3-030-36412-0_10
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N1708f8421666479f9f2ee5f869a31920 rdf:first sg:person.01130357621.02
60 rdf:rest Nf00695860a564ca9a916fa5f9c265604
61 N19a95dc83cae484b9f30d3d9de0ae7d0 schema:isbn 978-3-030-36411-3
62 978-3-030-36412-0
63 schema:name Combinatorial Optimization and Applications
64 rdf:type schema:Book
65 N1a05fc8afdc748878ee67508f2624ee8 rdf:first N358b72ed7ef3461387b9e18f4f10fef2
67 N24ccbf71caed43e1b753eea82e89e1d0 schema:name doi
68 schema:value 10.1007/978-3-030-36412-0_10
69 rdf:type schema:PropertyValue
70 N28d5b987727e43668e331091054f4614 schema:familyName Cardei
71 schema:givenName Mihaela
72 rdf:type schema:Person
73 N358b72ed7ef3461387b9e18f4f10fef2 schema:familyName Li
74 schema:givenName Yingshu
75 rdf:type schema:Person
76 N5cc70ee04ea74f0b910da58b08cc408a schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
79 rdf:rest Na4167b89b56140ce8b82fdd7e8582bb3
80 N6106ca8144f64c70ba88d441e2b0c2bc rdf:first sg:person.015273653637.29
81 rdf:rest rdf:nil
83 schema:value pub.1123154522
84 rdf:type schema:PropertyValue
85 N9b12b979989045419540d87e794e1f74 rdf:first sg:person.010555136403.19
87 Na4167b89b56140ce8b82fdd7e8582bb3 rdf:first Ndee8f88dea9641c3bdb3156421d707e3
88 rdf:rest rdf:nil
89 Na9492b244ae94d92b288e9f54bd269c7 schema:name Springer Nature
90 rdf:type schema:Organisation
92 rdf:rest N1708f8421666479f9f2ee5f869a31920
93 Ndee8f88dea9641c3bdb3156421d707e3 schema:familyName Huang
94 schema:givenName Yan
95 rdf:type schema:Person
96 Nf00695860a564ca9a916fa5f9c265604 rdf:first sg:person.01105113721.52
97 rdf:rest N6106ca8144f64c70ba88d441e2b0c2bc
98 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
99 schema:name Mathematical Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
102 schema:name Numerical and Computational Mathematics
103 rdf:type schema:DefinedTerm
104 sg:person.010555136403.19 schema:affiliation grid-institutes:grid.411963.8
105 schema:familyName Chen
106 schema:givenName Yong
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010555136403.19
108 rdf:type schema:Person
109 sg:person.01105113721.52 schema:affiliation grid-institutes:None
110 schema:familyName Wang
111 schema:givenName Lusheng
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
113 rdf:type schema:Person
114 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
115 schema:familyName Lin
116 schema:givenName Guohui
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
118 rdf:type schema:Person
119 sg:person.015273653637.29 schema:affiliation grid-institutes:grid.411963.8
120 schema:familyName Zhang
121 schema:givenName An
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015273653637.29
123 rdf:type schema:Person
124 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
125 schema:familyName Chen
126 schema:givenName Zhi-Zhong
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
128 rdf:type schema:Person
129 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR
130 schema:name Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR
131 rdf:type schema:Organization
132 grid-institutes:grid.17089.37 schema:alternateName Department of Computing Science, University of Alberta, Edmonton, Canada
133 schema:name Department of Computing Science, University of Alberta, Edmonton, Canada
134 rdf:type schema:Organization
135 grid-institutes:grid.411963.8 schema:alternateName Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
136 schema:name Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
137 rdf:type schema:Organization
138 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, Saitama, Japan
139 schema:name Division of Information System Design, Tokyo Denki University, Saitama, Japan
140 rdf:type schema:Organization