Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2015-08-04

AUTHORS

Marek Karpinski

ABSTRACT

We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the underlying paradigms and insights which lead to the recent improvements as well as some inherent obstacles for further progress on those problems. More... »

PAGES

3-11

Book

TITLE

Fundamentals of Computation Theory

ISBN

978-3-319-22176-2
978-3-319-22177-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-22177-9_1

DOI

http://dx.doi.org/10.1007/978-3-319-22177-9_1

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, 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"
      }
    ], 
    "datePublished": "2015-08-04", 
    "datePublishedReg": "2015-08-04", 
    "description": "We present in this paper some of the recent techniques and methods for proving best up\u00a0to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the underlying paradigms and insights which lead to the recent improvements as well as some inherent obstacles for further progress on those problems.", 
    "editor": [
      {
        "familyName": "Kosowski", 
        "givenName": "Adrian", 
        "type": "Person"
      }, 
      {
        "familyName": "Walukiewicz", 
        "givenName": "Igor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-22177-9_1", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-22176-2", 
        "978-3-319-22177-9"
      ], 
      "name": "Fundamentals of Computation Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "Traveling Salesman Problem", 
      "Asymmetric Traveling Salesman Problem", 
      "inapproximability bounds", 
      "salesman problem", 
      "Shortest Superstring", 
      "bounds", 
      "related problems", 
      "problem", 
      "recent techniques", 
      "superstring", 
      "maximum compression", 
      "further progress", 
      "inherent obstacles", 
      "recent improvements", 
      "dependency", 
      "technique", 
      "obstacles", 
      "progress", 
      "global dependencies", 
      "compression", 
      "paradigm", 
      "improvement", 
      "insights", 
      "light", 
      "challenges", 
      "paper", 
      "method"
    ], 
    "name": "Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies", 
    "pagination": "3-11", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042990202"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-22177-9_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-22177-9_1", 
      "https://app.dimensions.ai/details/publication/pub.1042990202"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:53", 
    "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_423.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-22177-9_1"
  }
]
 

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-319-22177-9_1'

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-319-22177-9_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-22177-9_1'

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-319-22177-9_1'


 

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

91 TRIPLES      22 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-22177-9_1 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Nc54ccd330e08423b8c4112210a8a81b8
4 schema:datePublished 2015-08-04
5 schema:datePublishedReg 2015-08-04
6 schema:description We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the underlying paradigms and insights which lead to the recent improvements as well as some inherent obstacles for further progress on those problems.
7 schema:editor Nb102e1df89dc4384934ee30cb315ef55
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nfae41290ec714b25ac6a50341bc9c272
11 schema:keywords Asymmetric Traveling Salesman Problem
12 Shortest Superstring
13 Traveling Salesman Problem
14 bounds
15 challenges
16 compression
17 dependency
18 further progress
19 global dependencies
20 improvement
21 inapproximability bounds
22 inherent obstacles
23 insights
24 light
25 maximum compression
26 method
27 obstacles
28 paper
29 paradigm
30 problem
31 progress
32 recent improvements
33 recent techniques
34 related problems
35 salesman problem
36 superstring
37 technique
38 schema:name Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies
39 schema:pagination 3-11
40 schema:productId N054b089d1f95416e8e8e2544caeff095
41 N348426e21a5447ef94f51c77fd485a8e
42 schema:publisher Nf83ab4d6aa6a4891ba327ff9647cac50
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042990202
44 https://doi.org/10.1007/978-3-319-22177-9_1
45 schema:sdDatePublished 2022-12-01T06:53
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher Na934b6c84c2c4dfe800bebcec8e2bd4b
48 schema:url https://doi.org/10.1007/978-3-319-22177-9_1
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N054b089d1f95416e8e8e2544caeff095 schema:name dimensions_id
53 schema:value pub.1042990202
54 rdf:type schema:PropertyValue
55 N348426e21a5447ef94f51c77fd485a8e schema:name doi
56 schema:value 10.1007/978-3-319-22177-9_1
57 rdf:type schema:PropertyValue
58 N60857e5e6fa04b5b8786d0c3aa33cd3d rdf:first Nb59105908cfb4a2bbb580ca2031de890
59 rdf:rest rdf:nil
60 N8467a98b0d334fd6ae1e7f808badafb3 schema:familyName Kosowski
61 schema:givenName Adrian
62 rdf:type schema:Person
63 Na934b6c84c2c4dfe800bebcec8e2bd4b schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Nb102e1df89dc4384934ee30cb315ef55 rdf:first N8467a98b0d334fd6ae1e7f808badafb3
66 rdf:rest N60857e5e6fa04b5b8786d0c3aa33cd3d
67 Nb59105908cfb4a2bbb580ca2031de890 schema:familyName Walukiewicz
68 schema:givenName Igor
69 rdf:type schema:Person
70 Nc54ccd330e08423b8c4112210a8a81b8 rdf:first sg:person.011636042271.02
71 rdf:rest rdf:nil
72 Nf83ab4d6aa6a4891ba327ff9647cac50 schema:name Springer Nature
73 rdf:type schema:Organisation
74 Nfae41290ec714b25ac6a50341bc9c272 schema:isbn 978-3-319-22176-2
75 978-3-319-22177-9
76 schema:name Fundamentals of Computation Theory
77 rdf:type schema:Book
78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
79 schema:name Mathematical Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
82 schema:name Applied Mathematics
83 rdf:type schema:DefinedTerm
84 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
85 schema:familyName Karpinski
86 schema:givenName Marek
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
88 rdf:type schema:Person
89 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, Bonn, Germany
90 schema:name Department of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, Bonn, Germany
91 rdf:type schema:Organization
 




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


...