Improved approximation algorithms for metric MaxTSP View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2006-12-08

AUTHORS

Zhi-Zhong Chen, Takayuki Nagoya

ABSTRACT

We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{27}{35}$$\end{document}. The other is for undirected graphs and its approximation ratio is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{7}{8}-o(1)$$\end{document}. Both algorithms improve on the previous bests. More... »

PAGES

321-336

References to SciGraph publications

  • 1986-03. Constructing a perfect matching is in random NC in COMBINATORICA
  • 1987-03. Matching is as easy as matrix inversion in COMBINATORICA
  • 1998-06-18. The Maximum Traveling Salesman Problem Under Polyhedral Norms in INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION
  • 2005-06. An Improved Randomized Approximation Algorithm for Max TSP in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-006-9023-7

    DOI

    http://dx.doi.org/10.1007/s10878-006-9023-7

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "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 Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
              "id": "http://www.grid.ac/institutes/grid.412773.4", 
              "name": [
                "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, 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 Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
              "id": "http://www.grid.ac/institutes/grid.412773.4", 
              "name": [
                "Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nagoya", 
            "givenName": "Takayuki", 
            "id": "sg:person.07642643114.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07642643114.94"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02579206", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029834600", 
              "https://doi.org/10.1007/bf02579206"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-69346-7_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019690175", 
              "https://doi.org/10.1007/3-540-69346-7_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579407", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019448085", 
              "https://doi.org/10.1007/bf02579407"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-005-1779-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012750855", 
              "https://doi.org/10.1007/s10878-005-1779-7"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006-12-08", 
        "datePublishedReg": "2006-12-08", 
        "description": "We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is \\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}$$\\frac{27}{35}$$\\end{document}. The other is for undirected graphs and its approximation ratio is \\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}$$\\frac{7}{8}-o(1)$$\\end{document}. Both algorithms improve on the previous bests.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10878-006-9023-7", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1036683", 
            "issn": [
              "1382-6905", 
              "1573-2886"
            ], 
            "name": "Journal of Combinatorial Optimization", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "13"
          }
        ], 
        "keywords": [
          "approximation algorithm", 
          "approximation ratio", 
          "polynomial-time approximation algorithm", 
          "metric case", 
          "undirected graph", 
          "previous bests", 
          "salesman problem", 
          "graph", 
          "algorithm", 
          "problem", 
          "BEST", 
          "cases", 
          "ratio"
        ], 
        "name": "Improved approximation algorithms for metric MaxTSP", 
        "pagination": "321-336", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1030832550"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10878-006-9023-7"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10878-006-9023-7", 
          "https://app.dimensions.ai/details/publication/pub.1030832550"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T09:54", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_423.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10878-006-9023-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-006-9023-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-006-9023-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10878-006-9023-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-006-9023-7'


     

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

    102 TRIPLES      22 PREDICATES      44 URIs      30 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-006-9023-7 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:0102
    4 anzsrc-for:0103
    5 schema:author N02720c3af1734222b1952450e8921412
    6 schema:citation sg:pub.10.1007/3-540-69346-7_15
    7 sg:pub.10.1007/bf02579206
    8 sg:pub.10.1007/bf02579407
    9 sg:pub.10.1007/s10878-005-1779-7
    10 schema:datePublished 2006-12-08
    11 schema:datePublishedReg 2006-12-08
    12 schema:description We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{27}{35}$$\end{document}. The other is for undirected graphs and its approximation ratio is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{7}{8}-o(1)$$\end{document}. Both algorithms improve on the previous bests.
    13 schema:genre article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree false
    16 schema:isPartOf Nb4c0d1b68ca64b358413ba8b98ec507d
    17 Nd87ba19e7b244e6c9b98955d4a0a4617
    18 sg:journal.1036683
    19 schema:keywords BEST
    20 algorithm
    21 approximation algorithm
    22 approximation ratio
    23 cases
    24 graph
    25 metric case
    26 polynomial-time approximation algorithm
    27 previous bests
    28 problem
    29 ratio
    30 salesman problem
    31 undirected graph
    32 schema:name Improved approximation algorithms for metric MaxTSP
    33 schema:pagination 321-336
    34 schema:productId N95cd3d148c374e63b6a06b844e1417ea
    35 Na7e17c5990c7437db0944372da00a727
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030832550
    37 https://doi.org/10.1007/s10878-006-9023-7
    38 schema:sdDatePublished 2022-05-10T09:54
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N355dbc1a6af2450081d714776bea3ab9
    41 schema:url https://doi.org/10.1007/s10878-006-9023-7
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N02720c3af1734222b1952450e8921412 rdf:first sg:person.015654265661.98
    46 rdf:rest N66d8ae17b6dd40e2914a5b0a4bae2c79
    47 N355dbc1a6af2450081d714776bea3ab9 schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N66d8ae17b6dd40e2914a5b0a4bae2c79 rdf:first sg:person.07642643114.94
    50 rdf:rest rdf:nil
    51 N95cd3d148c374e63b6a06b844e1417ea schema:name doi
    52 schema:value 10.1007/s10878-006-9023-7
    53 rdf:type schema:PropertyValue
    54 Na7e17c5990c7437db0944372da00a727 schema:name dimensions_id
    55 schema:value pub.1030832550
    56 rdf:type schema:PropertyValue
    57 Nb4c0d1b68ca64b358413ba8b98ec507d schema:volumeNumber 13
    58 rdf:type schema:PublicationVolume
    59 Nd87ba19e7b244e6c9b98955d4a0a4617 schema:issueNumber 4
    60 rdf:type schema:PublicationIssue
    61 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Mathematical Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Pure Mathematics
    66 rdf:type schema:DefinedTerm
    67 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Applied Mathematics
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Numerical and Computational Mathematics
    72 rdf:type schema:DefinedTerm
    73 sg:journal.1036683 schema:issn 1382-6905
    74 1573-2886
    75 schema:name Journal of Combinatorial Optimization
    76 schema:publisher Springer Nature
    77 rdf:type schema:Periodical
    78 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
    79 schema:familyName Chen
    80 schema:givenName Zhi-Zhong
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
    82 rdf:type schema:Person
    83 sg:person.07642643114.94 schema:affiliation grid-institutes:grid.412773.4
    84 schema:familyName Nagoya
    85 schema:givenName Takayuki
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07642643114.94
    87 rdf:type schema:Person
    88 sg:pub.10.1007/3-540-69346-7_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019690175
    89 https://doi.org/10.1007/3-540-69346-7_15
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/bf02579206 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029834600
    92 https://doi.org/10.1007/bf02579206
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/bf02579407 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019448085
    95 https://doi.org/10.1007/bf02579407
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/s10878-005-1779-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012750855
    98 https://doi.org/10.1007/s10878-005-1779-7
    99 rdf:type schema:CreativeWork
    100 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
    101 schema:name Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
    102 rdf:type schema:Organization
     




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


    ...