An Improved Approximation Algorithm for the Bandpass-2 Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Zhi-Zhong Chen , Lusheng Wang

ABSTRACT

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. More... »

PAGES

188-199

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31770-5_17

DOI

http://dx.doi.org/10.1007/978-3-642-31770-5_17

DIMENSIONS

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


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": "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

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/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
 




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


...