Improved Approximation Algorithms for Metric Max TSP View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

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

179-190

Book

TITLE

Algorithms – ESA 2005

ISBN

978-3-540-29118-3
978-3-540-31951-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11561071_18

DOI

http://dx.doi.org/10.1007/11561071_18

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Dept. of Math. Sci., Tokyo Denki Univ., 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": "Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Dept. of Math. Sci., Tokyo Denki Univ., 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"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "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.", 
    "editor": [
      {
        "familyName": "Brodal", 
        "givenName": "Gerth St\u00f8lting", 
        "type": "Person"
      }, 
      {
        "familyName": "Leonardi", 
        "givenName": "Stefano", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11561071_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29118-3", 
        "978-3-540-31951-1"
      ], 
      "name": "Algorithms \u2013 ESA 2005", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation algorithm", 
      "approximation ratio", 
      "polynomial-time approximation algorithm", 
      "metric case", 
      "undirected graph", 
      "previous bests", 
      "salesman problem", 
      "Max TSP", 
      "graph", 
      "algorithm", 
      "problem", 
      "TSP", 
      "BEST", 
      "cases", 
      "ratio"
    ], 
    "name": "Improved Approximation Algorithms for Metric Max TSP", 
    "pagination": "179-190", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040392463"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11561071_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11561071_18", 
      "https://app.dimensions.ai/details/publication/pub.1040392463"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:48", 
    "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/chapter/chapter_365.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11561071_18"
  }
]
 

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/11561071_18'

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/11561071_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11561071_18'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11561071_18'


 

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

87 TRIPLES      23 PREDICATES      41 URIs      34 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11561071_18 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N0ef9f76030cf4f6bad23bde5165263cf
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 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.
7 schema:editor N05ce72defcc742c8a06479779e1e05a2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nce598a510e72479eb2bce5fdf200ad71
12 schema:keywords BEST
13 Max TSP
14 TSP
15 algorithm
16 approximation algorithm
17 approximation ratio
18 cases
19 graph
20 metric case
21 polynomial-time approximation algorithm
22 previous bests
23 problem
24 ratio
25 salesman problem
26 undirected graph
27 schema:name Improved Approximation Algorithms for Metric Max TSP
28 schema:pagination 179-190
29 schema:productId Ne907848c00c84c21b4b83196ff314daa
30 Ne9ee3ff19db0428c8b348cda9f2deed4
31 schema:publisher Nad2662b0dad4428daab1242dc20a220d
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040392463
33 https://doi.org/10.1007/11561071_18
34 schema:sdDatePublished 2022-05-10T10:48
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N6f5241e185744e728a57bfd430e8f274
37 schema:url https://doi.org/10.1007/11561071_18
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N05ce72defcc742c8a06479779e1e05a2 rdf:first N24116d6a529d49aeba4cd669a45f8e05
42 rdf:rest N8f08813396a349cabd64e2686aa0b65e
43 N0ef9f76030cf4f6bad23bde5165263cf rdf:first sg:person.015654265661.98
44 rdf:rest N780221c5fd604d6babc12df34dce1c09
45 N24116d6a529d49aeba4cd669a45f8e05 schema:familyName Brodal
46 schema:givenName Gerth Stølting
47 rdf:type schema:Person
48 N6f5241e185744e728a57bfd430e8f274 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N780221c5fd604d6babc12df34dce1c09 rdf:first sg:person.07642643114.94
51 rdf:rest rdf:nil
52 N8f08813396a349cabd64e2686aa0b65e rdf:first Ncac13e63b22b466aabbe0e4f1b24b52d
53 rdf:rest rdf:nil
54 Nad2662b0dad4428daab1242dc20a220d schema:name Springer Nature
55 rdf:type schema:Organisation
56 Ncac13e63b22b466aabbe0e4f1b24b52d schema:familyName Leonardi
57 schema:givenName Stefano
58 rdf:type schema:Person
59 Nce598a510e72479eb2bce5fdf200ad71 schema:isbn 978-3-540-29118-3
60 978-3-540-31951-1
61 schema:name Algorithms – ESA 2005
62 rdf:type schema:Book
63 Ne907848c00c84c21b4b83196ff314daa schema:name dimensions_id
64 schema:value pub.1040392463
65 rdf:type schema:PropertyValue
66 Ne9ee3ff19db0428c8b348cda9f2deed4 schema:name doi
67 schema:value 10.1007/11561071_18
68 rdf:type schema:PropertyValue
69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
70 schema:name Information and Computing Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
73 schema:name Computation Theory and Mathematics
74 rdf:type schema:DefinedTerm
75 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
76 schema:familyName Chen
77 schema:givenName Zhi-Zhong
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
79 rdf:type schema:Person
80 sg:person.07642643114.94 schema:affiliation grid-institutes:grid.412773.4
81 schema:familyName Nagoya
82 schema:givenName Takayuki
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07642643114.94
84 rdf:type schema:Person
85 grid-institutes:grid.412773.4 schema:alternateName Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
86 schema:name Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
87 rdf:type schema:Organization
 




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


...