A randomized approximation algorithm for metric triangle packing View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2020-10-13

AUTHORS

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

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-ϵ\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... »

PAGES

12-27

References to SciGraph publications

  • 2012-05-15. Partition Into Triangles on Bounded Degree Graphs in THEORY OF COMPUTING SYSTEMS
  • 2014-07-22. Approximating the $$k$$ -Set Packing Problem by Local Improvements in COMBINATORIAL OPTIMIZATION
  • 2000. A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs in ALGORITHM THEORY - SWAT 2000
  • 1998. The Vertex-Disjoint Triangles Problem in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 2003-05-13. Approximation Hardness for Small Occurrence Instances of NP-Hard Problems in ALGORITHMS AND COMPLEXITY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-020-00660-7

    DOI

    http://dx.doi.org/10.1007/s10878-020-00660-7

    DIMENSIONS

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


    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: 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

    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/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

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-020-00660-7 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author Na9bf3b13695a4cd48ccb48a46735ca04
    4 schema:citation sg:pub.10.1007/10692760_3
    5 sg:pub.10.1007/3-540-44849-7_21
    6 sg:pub.10.1007/3-540-44985-x_19
    7 sg:pub.10.1007/978-3-319-14115-2_35
    8 sg:pub.10.1007/s00224-012-9412-5
    9 schema:datePublished 2020-10-13
    10 schema:datePublishedReg 2020-10-13
    11 schema: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-ϵ\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}.
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N301f19ae22b548d0bd79200ba17cb5e2
    16 N54870f355d2043cc834bb45193327080
    17 sg:journal.1036683
    18 schema:keywords algorithm
    19 approximation algorithm
    20 approximation ratio
    21 cases
    22 collection
    23 complete graph G
    24 edge
    25 expected approximation ratio
    26 graph
    27 graph G
    28 inequality
    29 input graph
    30 literature
    31 metric case
    32 n triangles
    33 nontrivial approximation algorithm
    34 packing
    35 packing problem
    36 paper
    37 polynomial-time approximation algorithm
    38 problem
    39 randomized approximation algorithm
    40 ratio
    41 total weight
    42 triangle
    43 triangle inequality
    44 triangle packing
    45 triangle packing problem
    46 vertex-disjoint triangles
    47 vertices
    48 weight
    49 work
    50 schema:name A randomized approximation algorithm for metric triangle packing
    51 schema:pagination 12-27
    52 schema:productId N0e89d326115249f8a9941faa07d2b85d
    53 N58c5b3100dd74fb192d7552b1fb71827
    54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1131654837
    55 https://doi.org/10.1007/s10878-020-00660-7
    56 schema:sdDatePublished 2022-05-20T07:37
    57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    58 schema:sdPublisher Nfed4dd418be342db84ad1cf6afbae0be
    59 schema:url https://doi.org/10.1007/s10878-020-00660-7
    60 sgo:license sg:explorer/license/
    61 sgo:sdDataset articles
    62 rdf:type schema:ScholarlyArticle
    63 N0e89d326115249f8a9941faa07d2b85d schema:name doi
    64 schema:value 10.1007/s10878-020-00660-7
    65 rdf:type schema:PropertyValue
    66 N301f19ae22b548d0bd79200ba17cb5e2 schema:volumeNumber 41
    67 rdf:type schema:PublicationVolume
    68 N38684110e4d84aaf86a3eba895077576 rdf:first sg:person.01130357621.02
    69 rdf:rest Nca5a34a4168442c6863b518f9c1223e0
    70 N54870f355d2043cc834bb45193327080 schema:issueNumber 1
    71 rdf:type schema:PublicationIssue
    72 N58c5b3100dd74fb192d7552b1fb71827 schema:name dimensions_id
    73 schema:value pub.1131654837
    74 rdf:type schema:PropertyValue
    75 N8e097750fec3430f974f73c29a93b511 rdf:first sg:person.015273653637.29
    76 rdf:rest rdf:nil
    77 Na9bf3b13695a4cd48ccb48a46735ca04 rdf:first sg:person.010555136403.19
    78 rdf:rest Nd73a1fca2c0f49e099d34556ec0087de
    79 Nca5a34a4168442c6863b518f9c1223e0 rdf:first sg:person.01105113721.52
    80 rdf:rest N8e097750fec3430f974f73c29a93b511
    81 Nd73a1fca2c0f49e099d34556ec0087de rdf:first sg:person.015654265661.98
    82 rdf:rest N38684110e4d84aaf86a3eba895077576
    83 Nfed4dd418be342db84ad1cf6afbae0be schema:name Springer Nature - SN SciGraph project
    84 rdf:type schema:Organization
    85 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Mathematical Sciences
    87 rdf:type schema:DefinedTerm
    88 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Numerical and Computational Mathematics
    90 rdf:type schema:DefinedTerm
    91 sg:grant.7538013 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00660-7
    92 rdf:type schema:MonetaryGrant
    93 sg:grant.8124106 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00660-7
    94 rdf:type schema:MonetaryGrant
    95 sg:grant.8132243 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00660-7
    96 rdf:type schema:MonetaryGrant
    97 sg:grant.8898306 http://pending.schema.org/fundedItem sg:pub.10.1007/s10878-020-00660-7
    98 rdf:type schema:MonetaryGrant
    99 sg:journal.1036683 schema:issn 1382-6905
    100 1573-2886
    101 schema:name Journal of Combinatorial Optimization
    102 schema:publisher Springer Nature
    103 rdf:type schema:Periodical
    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:grid.35030.35
    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 sg:pub.10.1007/10692760_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015750643
    130 https://doi.org/10.1007/10692760_3
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/3-540-44849-7_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008906886
    133 https://doi.org/10.1007/3-540-44849-7_21
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/3-540-44985-x_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051241645
    136 https://doi.org/10.1007/3-540-44985-x_19
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/978-3-319-14115-2_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089701136
    139 https://doi.org/10.1007/978-3-319-14115-2_35
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/s00224-012-9412-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046943879
    142 https://doi.org/10.1007/s00224-012-9412-5
    143 rdf:type schema:CreativeWork
    144 grid-institutes:grid.17089.37 schema:alternateName Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
    145 schema:name Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, AB, Canada
    146 rdf:type schema:Organization
    147 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China
    148 schema:name Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China
    149 rdf:type schema:Organization
    150 grid-institutes:grid.411963.8 schema:alternateName Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
    151 schema:name Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China
    152 rdf:type schema:Organization
    153 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, Saitama, Japan
    154 schema:name Division of Information System Design, Tokyo Denki University, Saitama, Japan
    155 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...