Ontology type: schema:ScholarlyArticle
2006-12-08
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... »
PAGES321-336
http://scigraph.springernature.com/pub.10.1007/s10878-006-9023-7
DOIhttp://dx.doi.org/10.1007/s10878-006-9023-7
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1030832550
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
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