Ontology type: schema:ScholarlyArticle
2020-10-13
AUTHORSYong Chen, Zhi-Zhong Chen, Guohui Lin, Lusheng Wang, An Zhang
ABSTRACTGiven 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-ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0.66768 - \epsilon $$\end{document} for any constant ϵ>0\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... »
PAGES12-27
http://scigraph.springernature.com/pub.10.1007/s10878-020-00660-7
DOIhttp://dx.doi.org/10.1007/s10878-020-00660-7
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1131654837
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"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, T6G 2E8, Edmonton, AB, Canada",
"id": "http://www.grid.ac/institutes/grid.17089.37",
"name": [
"Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, 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, Hong Kong SAR, China",
"id": "http://www.grid.ac/institutes/grid.35030.35",
"name": [
"Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China"
],
"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"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-319-14115-2_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1089701136",
"https://doi.org/10.1007/978-3-319-14115-2_35"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-012-9412-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046943879",
"https://doi.org/10.1007/s00224-012-9412-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-44985-x_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1051241645",
"https://doi.org/10.1007/3-540-44985-x_19"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/10692760_3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015750643",
"https://doi.org/10.1007/10692760_3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-44849-7_21",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008906886",
"https://doi.org/10.1007/3-540-44849-7_21"
],
"type": "CreativeWork"
}
],
"datePublished": "2020-10-13",
"datePublishedReg": "2020-10-13",
"description": "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-\u03f5\\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.66768 - \\epsilon $$\\end{document} for any constant \u03f5>0\\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}.",
"genre": "article",
"id": "sg:pub.10.1007/s10878-020-00660-7",
"inLanguage": "en",
"isAccessibleForFree": false,
"isFundedItemOf": [
{
"id": "sg:grant.8124106",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8898306",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.7538013",
"type": "MonetaryGrant"
},
{
"id": "sg:grant.8132243",
"type": "MonetaryGrant"
}
],
"isPartOf": [
{
"id": "sg:journal.1036683",
"issn": [
"1382-6905",
"1573-2886"
],
"name": "Journal of Combinatorial Optimization",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "41"
}
],
"keywords": [
"triangle packing problem",
"approximation algorithm",
"polynomial-time approximation algorithm",
"packing problem",
"vertex-disjoint triangles",
"metric case",
"expected approximation ratio",
"randomized approximation algorithm",
"graph G",
"nontrivial approximation algorithm",
"input graph",
"triangle inequality",
"approximation ratio",
"triangle packing",
"problem",
"n triangles",
"algorithm",
"complete graph G",
"vertices",
"graph",
"triangle",
"edge",
"inequality",
"total weight",
"work",
"cases",
"literature",
"ratio",
"packing",
"collection",
"weight",
"paper"
],
"name": "A randomized approximation algorithm for metric triangle packing",
"pagination": "12-27",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1131654837"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10878-020-00660-7"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10878-020-00660-7",
"https://app.dimensions.ai/details/publication/pub.1131654837"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:37",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_862.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s10878-020-00660-7"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s10878-020-00660-7'
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/s10878-020-00660-7'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-020-00660-7'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10878-020-00660-7'
This table displays all metadata directly associated to this object as RDF triples.
155 TRIPLES
22 PREDICATES
62 URIs
49 LITERALS
6 BLANK NODES