New Inapproximability Bounds for TSP View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Marek Karpinski , Michael Lampis , Richard Schmied

ABSTRACT

In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results. More... »

PAGES

568-578

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-45030-3_53

DOI

http://dx.doi.org/10.1007/978-3-642-45030-3_53

DIMENSIONS

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


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/09", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Engineering", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0906", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Electrical and Electronic Engineering", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan", 
          "id": "http://www.grid.ac/institutes/grid.258799.8", 
          "name": [
            "Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lampis", 
        "givenName": "Michael", 
        "id": "sg:person.015655605717.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015655605717.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schmied", 
        "givenName": "Richard", 
        "id": "sg:person.011721753177.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011721753177.01"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.", 
    "editor": [
      {
        "familyName": "Cai", 
        "givenName": "Leizhen", 
        "type": "Person"
      }, 
      {
        "familyName": "Cheng", 
        "givenName": "Siu-Wing", 
        "type": "Person"
      }, 
      {
        "familyName": "Lam", 
        "givenName": "Tak-Wah", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-45030-3_53", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-45029-7", 
        "978-3-642-45030-3"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "new construction", 
      "hardness", 
      "amplifier", 
      "first improvement", 
      "asymmetric case", 
      "problem", 
      "construction", 
      "bounds", 
      "symmetric case", 
      "reduction", 
      "improvement", 
      "results", 
      "Traveling Salesman Problem", 
      "cases", 
      "main tool", 
      "tool", 
      "interest", 
      "salesman problem", 
      "decades", 
      "Asymmetric Traveling Salesman Problem", 
      "proof", 
      "approximation bounds", 
      "metric traveling salesman problem", 
      "paper", 
      "approximability", 
      "independent interest", 
      "inapproximability bounds"
    ], 
    "name": "New Inapproximability Bounds for TSP", 
    "pagination": "568-578", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041344548"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-45030-3_53"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-45030-3_53", 
      "https://app.dimensions.ai/details/publication/pub.1041344548"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_470.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-45030-3_53"
  }
]
 

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-45030-3_53'

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-45030-3_53'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-45030-3_53'

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-45030-3_53'


 

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

115 TRIPLES      22 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-45030-3_53 schema:about anzsrc-for:09
2 anzsrc-for:0906
3 schema:author N9d974c0eedd54db2be8daeb65b0899ec
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.
7 schema:editor N15b8076f9e984739a6e5f4c77608cf70
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nd6b7f16ba68643ed9f82eaf890eb76c4
11 schema:keywords Asymmetric Traveling Salesman Problem
12 Traveling Salesman Problem
13 amplifier
14 approximability
15 approximation bounds
16 asymmetric case
17 bounds
18 cases
19 construction
20 decades
21 first improvement
22 hardness
23 improvement
24 inapproximability bounds
25 independent interest
26 interest
27 main tool
28 metric traveling salesman problem
29 new construction
30 paper
31 problem
32 proof
33 reduction
34 results
35 salesman problem
36 symmetric case
37 tool
38 schema:name New Inapproximability Bounds for TSP
39 schema:pagination 568-578
40 schema:productId N6cc985ae3ec94fab8fbf08b47ffc4ea3
41 Ndfc5e841337b4cf3a9f5dcb66dd7f785
42 schema:publisher N26d0e1165d54495dbcc1b31175cbce5a
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041344548
44 https://doi.org/10.1007/978-3-642-45030-3_53
45 schema:sdDatePublished 2022-12-01T06:54
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher Nd1ed25b579924d6a8f933722595129fa
48 schema:url https://doi.org/10.1007/978-3-642-45030-3_53
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N15b8076f9e984739a6e5f4c77608cf70 rdf:first N294b2286adee4f919522d7a5c6fef80f
53 rdf:rest N25bca2caf2c943beab1353b3549c2b68
54 N25bca2caf2c943beab1353b3549c2b68 rdf:first Nfd1095db0da741ddb55175df301822ce
55 rdf:rest N62553aeb61ca429cbc69af9c01154bba
56 N26d0e1165d54495dbcc1b31175cbce5a schema:name Springer Nature
57 rdf:type schema:Organisation
58 N294b2286adee4f919522d7a5c6fef80f schema:familyName Cai
59 schema:givenName Leizhen
60 rdf:type schema:Person
61 N52cffd07b9e84b9783d92a176620e5d6 schema:familyName Lam
62 schema:givenName Tak-Wah
63 rdf:type schema:Person
64 N62177af54645420f83d0b0ab5decb1f7 rdf:first sg:person.015655605717.07
65 rdf:rest Nc60202aa5dbc4afb980c0f9953dfb183
66 N62553aeb61ca429cbc69af9c01154bba rdf:first N52cffd07b9e84b9783d92a176620e5d6
67 rdf:rest rdf:nil
68 N6cc985ae3ec94fab8fbf08b47ffc4ea3 schema:name doi
69 schema:value 10.1007/978-3-642-45030-3_53
70 rdf:type schema:PropertyValue
71 N9d974c0eedd54db2be8daeb65b0899ec rdf:first sg:person.011636042271.02
72 rdf:rest N62177af54645420f83d0b0ab5decb1f7
73 Nc60202aa5dbc4afb980c0f9953dfb183 rdf:first sg:person.011721753177.01
74 rdf:rest rdf:nil
75 Nd1ed25b579924d6a8f933722595129fa schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Nd6b7f16ba68643ed9f82eaf890eb76c4 schema:isbn 978-3-642-45029-7
78 978-3-642-45030-3
79 schema:name Algorithms and Computation
80 rdf:type schema:Book
81 Ndfc5e841337b4cf3a9f5dcb66dd7f785 schema:name dimensions_id
82 schema:value pub.1041344548
83 rdf:type schema:PropertyValue
84 Nfd1095db0da741ddb55175df301822ce schema:familyName Cheng
85 schema:givenName Siu-Wing
86 rdf:type schema:Person
87 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
88 schema:name Engineering
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0906 schema:inDefinedTermSet anzsrc-for:
91 schema:name Electrical and Electronic Engineering
92 rdf:type schema:DefinedTerm
93 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
94 schema:familyName Karpinski
95 schema:givenName Marek
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
97 rdf:type schema:Person
98 sg:person.011721753177.01 schema:affiliation grid-institutes:grid.10388.32
99 schema:familyName Schmied
100 schema:givenName Richard
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011721753177.01
102 rdf:type schema:Person
103 sg:person.015655605717.07 schema:affiliation grid-institutes:grid.258799.8
104 schema:familyName Lampis
105 schema:givenName Michael
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015655605717.07
107 rdf:type schema:Person
108 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, Germany
109 Dept. of Computer Science, University of Bonn, Germany
110 schema:name Dept. of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, Germany
111 Dept. of Computer Science, University of Bonn, Germany
112 rdf:type schema:Organization
113 grid-institutes:grid.258799.8 schema:alternateName Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan
114 schema:name Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan
115 rdf:type schema:Organization
 




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


...