Ontology type: schema:Chapter Open Access: True
2005
AUTHORSZhi-Zhong Chen , Takayuki Nagoya
ABSTRACTWe 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... »
PAGES179-190
Algorithms – ESA 2005
ISBN
978-3-540-29118-3
978-3-540-31951-1
http://scigraph.springernature.com/pub.10.1007/11561071_18
DOIhttp://dx.doi.org/10.1007/11561071_18
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1040392463
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
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