Ontology type: schema:Chapter
2012
AUTHORS ABSTRACTThe bandpass-2 problem (Bandpass-2, for short) is a generalization of the maximum traveling salesman problem (Max TSP, for short). Of particular interest is the difference between the two problems, where the edge weights in Bandpass-2 are dynamic rather than given at the front. A trivial approximation algorithm for Bandpass-2 can achieve a ratio of 0.5. Recently, Tong et al. [19] have presented a nontrivial approximation algorithm for Bandpass-2 that achieves a ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{21}{40}$\end{document}. In this paper, we present a new approximation algorithm that achieves a ratio of 0.5318. More... »
PAGES188-199
Combinatorial Optimization and Applications
ISBN
978-3-642-31769-9
978-3-642-31770-5
http://scigraph.springernature.com/pub.10.1007/978-3-642-31770-5_17
DOIhttp://dx.doi.org/10.1007/978-3-642-31770-5_17
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1005862633
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": "Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, 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 SAR",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
],
"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"
}
],
"datePublished": "2012",
"datePublishedReg": "2012-01-01",
"description": "The bandpass-2 problem (Bandpass-2, for short) is a generalization of the maximum traveling salesman problem (Max TSP, for short). Of particular interest is the difference between the two problems, where the edge weights in Bandpass-2 are dynamic rather than given at the front. A trivial approximation algorithm for Bandpass-2 can achieve a ratio of\u00a00.5. Recently, Tong et al. [19] have presented a nontrivial approximation algorithm for Bandpass-2 that achieves a ratio of \\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{21}{40}$\\end{document}. In this paper, we present a new approximation algorithm that achieves a ratio of 0.5318.",
"editor": [
{
"familyName": "Lin",
"givenName": "Guohui",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-31770-5_17",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-642-31769-9",
"978-3-642-31770-5"
],
"name": "Combinatorial Optimization and Applications",
"type": "Book"
},
"keywords": [
"approximation algorithm",
"problem",
"generalization",
"salesman problem",
"particular interest",
"interest",
"edge weights",
"front",
"algorithm",
"ratio",
"Tong",
"al",
"nontrivial approximation algorithm",
"new approximation algorithm",
"improved approximation algorithms",
"differences",
"weight",
"paper"
],
"name": "An Improved Approximation Algorithm for the Bandpass-2 Problem",
"pagination": "188-199",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1005862633"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-31770-5_17"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-31770-5_17",
"https://app.dimensions.ai/details/publication/pub.1005862633"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:42",
"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/chapter/chapter_170.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-31770-5_17"
}
]
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/978-3-642-31770-5_17'
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/978-3-642-31770-5_17'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31770-5_17'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31770-5_17'
This table displays all metadata directly associated to this object as RDF triples.
88 TRIPLES
23 PREDICATES
44 URIs
37 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-3-642-31770-5_17 | schema:about | anzsrc-for:01 |
2 | ″ | ″ | anzsrc-for:0103 |
3 | ″ | schema:author | N3ed0069c6450470a98b379064b3e2a57 |
4 | ″ | schema:datePublished | 2012 |
5 | ″ | schema:datePublishedReg | 2012-01-01 |
6 | ″ | schema:description | The bandpass-2 problem (Bandpass-2, for short) is a generalization of the maximum traveling salesman problem (Max TSP, for short). Of particular interest is the difference between the two problems, where the edge weights in Bandpass-2 are dynamic rather than given at the front. A trivial approximation algorithm for Bandpass-2 can achieve a ratio of 0.5. Recently, Tong et al. [19] have presented a nontrivial approximation algorithm for Bandpass-2 that achieves a ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{21}{40}$\end{document}. In this paper, we present a new approximation algorithm that achieves a ratio of 0.5318. |
7 | ″ | schema:editor | N419960ebe6694c03a3b18496d58b4af2 |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | false |
11 | ″ | schema:isPartOf | N45570f1b27254445bc1f1460f912db1a |
12 | ″ | schema:keywords | Tong |
13 | ″ | ″ | al |
14 | ″ | ″ | algorithm |
15 | ″ | ″ | approximation algorithm |
16 | ″ | ″ | differences |
17 | ″ | ″ | edge weights |
18 | ″ | ″ | front |
19 | ″ | ″ | generalization |
20 | ″ | ″ | improved approximation algorithms |
21 | ″ | ″ | interest |
22 | ″ | ″ | new approximation algorithm |
23 | ″ | ″ | nontrivial approximation algorithm |
24 | ″ | ″ | paper |
25 | ″ | ″ | particular interest |
26 | ″ | ″ | problem |
27 | ″ | ″ | ratio |
28 | ″ | ″ | salesman problem |
29 | ″ | ″ | weight |
30 | ″ | schema:name | An Improved Approximation Algorithm for the Bandpass-2 Problem |
31 | ″ | schema:pagination | 188-199 |
32 | ″ | schema:productId | N6c678f9d76cf4db19040a96edbb6e7ed |
33 | ″ | ″ | Na974ec6806e24b569192d5da16c30302 |
34 | ″ | schema:publisher | N40565980597d4e749d561bf0a45424e6 |
35 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1005862633 |
36 | ″ | ″ | https://doi.org/10.1007/978-3-642-31770-5_17 |
37 | ″ | schema:sdDatePublished | 2022-05-20T07:42 |
38 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
39 | ″ | schema:sdPublisher | Na8213fb4449442319ee1e550d9523f40 |
40 | ″ | schema:url | https://doi.org/10.1007/978-3-642-31770-5_17 |
41 | ″ | sgo:license | sg:explorer/license/ |
42 | ″ | sgo:sdDataset | chapters |
43 | ″ | rdf:type | schema:Chapter |
44 | N06bb708c6f084a4c9a5fd04b53acbce3 | schema:familyName | Lin |
45 | ″ | schema:givenName | Guohui |
46 | ″ | rdf:type | schema:Person |
47 | N3da2d0799a964736afb4ab9c3e26e11d | rdf:first | sg:person.01105113721.52 |
48 | ″ | rdf:rest | rdf:nil |
49 | N3ed0069c6450470a98b379064b3e2a57 | rdf:first | sg:person.015654265661.98 |
50 | ″ | rdf:rest | N3da2d0799a964736afb4ab9c3e26e11d |
51 | N40565980597d4e749d561bf0a45424e6 | schema:name | Springer Nature |
52 | ″ | rdf:type | schema:Organisation |
53 | N419960ebe6694c03a3b18496d58b4af2 | rdf:first | N06bb708c6f084a4c9a5fd04b53acbce3 |
54 | ″ | rdf:rest | rdf:nil |
55 | N45570f1b27254445bc1f1460f912db1a | schema:isbn | 978-3-642-31769-9 |
56 | ″ | ″ | 978-3-642-31770-5 |
57 | ″ | schema:name | Combinatorial Optimization and Applications |
58 | ″ | rdf:type | schema:Book |
59 | N6c678f9d76cf4db19040a96edbb6e7ed | schema:name | dimensions_id |
60 | ″ | schema:value | pub.1005862633 |
61 | ″ | rdf:type | schema:PropertyValue |
62 | Na8213fb4449442319ee1e550d9523f40 | schema:name | Springer Nature - SN SciGraph project |
63 | ″ | rdf:type | schema:Organization |
64 | Na974ec6806e24b569192d5da16c30302 | schema:name | doi |
65 | ″ | schema:value | 10.1007/978-3-642-31770-5_17 |
66 | ″ | rdf:type | schema:PropertyValue |
67 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |
68 | ″ | schema:name | Mathematical Sciences |
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:person.01105113721.52 | schema:affiliation | grid-institutes:None |
74 | ″ | schema:familyName | Wang |
75 | ″ | schema:givenName | Lusheng |
76 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52 |
77 | ″ | rdf:type | schema:Person |
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 | grid-institutes:None | schema:alternateName | Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR |
84 | ″ | schema:name | Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR |
85 | ″ | rdf:type | schema:Organization |
86 | grid-institutes:grid.412773.4 | schema:alternateName | Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan |
87 | ″ | schema:name | Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan |
88 | ″ | rdf:type | schema:Organization |