An Improved Randomized Approximation Algorithm for Max TSP View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2005-06

AUTHORS

Zhi-Zhong Chen, Lusheng Wang

ABSTRACT

We present an O(n3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{251}{331}$$\end{document}, where n is the number of vertices in the input (undirected) graph. This improves the previous best.

PAGES

401-432

References to SciGraph publications

  • 1998-06-18. The Maximum Traveling Salesman Problem Under Polyhedral Norms in INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10878-005-1779-7

    DOI

    http://dx.doi.org/10.1007/s10878-005-1779-7

    DIMENSIONS

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


    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 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 Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong", 
              "id": "http://www.grid.ac/institutes/grid.35030.35", 
              "name": [
                "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"
              ], 
              "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"
          }
        ], 
        "citation": [
          {
            "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"
          }
        ], 
        "datePublished": "2005-06", 
        "datePublishedReg": "2005-06-01", 
        "description": "We present an O(n3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically \\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{251}{331}$$\\end{document}, where n is the number of vertices in the input (undirected) graph. This improves the previous best.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10878-005-1779-7", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "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": "9"
          }
        ], 
        "keywords": [
          "randomized approximation algorithm", 
          "approximation algorithm", 
          "number of vertices", 
          "input graph", 
          "salesman problem", 
          "approximation ratio", 
          "Max TSP", 
          "algorithm", 
          "vertices", 
          "graph", 
          "problem", 
          "TSP", 
          "number", 
          "ratio"
        ], 
        "name": "An Improved Randomized Approximation Algorithm for Max TSP", 
        "pagination": "401-432", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1012750855"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10878-005-1779-7"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10878-005-1779-7", 
          "https://app.dimensions.ai/details/publication/pub.1012750855"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:23", 
        "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_393.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10878-005-1779-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-005-1779-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-005-1779-7'

    Turtle is a human-readable linked data format.

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


     

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

    86 TRIPLES      22 PREDICATES      41 URIs      32 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10878-005-1779-7 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N32b165ecaf9d4b57bfbee77ba534edc5
    4 schema:citation sg:pub.10.1007/3-540-69346-7_15
    5 schema:datePublished 2005-06
    6 schema:datePublishedReg 2005-06-01
    7 schema:description We present an O(n3)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{251}{331}$$\end{document}, where n is the number of vertices in the input (undirected) graph. This improves the previous best.
    8 schema:genre article
    9 schema:inLanguage en
    10 schema:isAccessibleForFree true
    11 schema:isPartOf N48f6d0a8fe6d45a9925b2c0fc979a7c6
    12 N7538db95a2004c58b01a92f72c510467
    13 sg:journal.1036683
    14 schema:keywords Max TSP
    15 TSP
    16 algorithm
    17 approximation algorithm
    18 approximation ratio
    19 graph
    20 input graph
    21 number
    22 number of vertices
    23 problem
    24 randomized approximation algorithm
    25 ratio
    26 salesman problem
    27 vertices
    28 schema:name An Improved Randomized Approximation Algorithm for Max TSP
    29 schema:pagination 401-432
    30 schema:productId Ne3a107ba527b4d68bd62efd99794fb19
    31 Ne3f37c20616b4651be5abd2d193933db
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012750855
    33 https://doi.org/10.1007/s10878-005-1779-7
    34 schema:sdDatePublished 2022-05-20T07:23
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher Nc2f6dd0f568847278fd6b973aabe14ff
    37 schema:url https://doi.org/10.1007/s10878-005-1779-7
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset articles
    40 rdf:type schema:ScholarlyArticle
    41 N32b165ecaf9d4b57bfbee77ba534edc5 rdf:first sg:person.015654265661.98
    42 rdf:rest N4916dc7a567a4653b961b125928988c5
    43 N48f6d0a8fe6d45a9925b2c0fc979a7c6 schema:volumeNumber 9
    44 rdf:type schema:PublicationVolume
    45 N4916dc7a567a4653b961b125928988c5 rdf:first sg:person.01105113721.52
    46 rdf:rest rdf:nil
    47 N7538db95a2004c58b01a92f72c510467 schema:issueNumber 4
    48 rdf:type schema:PublicationIssue
    49 Nc2f6dd0f568847278fd6b973aabe14ff schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 Ne3a107ba527b4d68bd62efd99794fb19 schema:name dimensions_id
    52 schema:value pub.1012750855
    53 rdf:type schema:PropertyValue
    54 Ne3f37c20616b4651be5abd2d193933db schema:name doi
    55 schema:value 10.1007/s10878-005-1779-7
    56 rdf:type schema:PropertyValue
    57 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    58 schema:name Mathematical Sciences
    59 rdf:type schema:DefinedTerm
    60 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    61 schema:name Numerical and Computational Mathematics
    62 rdf:type schema:DefinedTerm
    63 sg:journal.1036683 schema:issn 1382-6905
    64 1573-2886
    65 schema:name Journal of Combinatorial Optimization
    66 schema:publisher Springer Nature
    67 rdf:type schema:Periodical
    68 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
    69 schema:familyName Wang
    70 schema:givenName Lusheng
    71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
    72 rdf:type schema:Person
    73 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
    74 schema:familyName Chen
    75 schema:givenName Zhi-Zhong
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
    77 rdf:type schema:Person
    78 sg:pub.10.1007/3-540-69346-7_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019690175
    79 https://doi.org/10.1007/3-540-69346-7_15
    80 rdf:type schema:CreativeWork
    81 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
    82 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong
    83 rdf:type schema:Organization
    84 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
    85 schema:name Department of Mathematical Sciences, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
    86 rdf:type schema:Organization
     




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


    ...