Approximation Hardness of TSP with Bounded Metrics View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-07-04

AUTHORS

Lars Engebretsen , Marek Karpinski

ABSTRACT

The general asymmetric (and metric) TSP is known to be approximable only to within an O(log n) factor, and is also known to be approximable within a constant factor as soon as the metric is bounded. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics and prove approximation lower bounds of 101/100 and 203/202, respectively, for these problems. We prove also approximation lower bounds of 321/320 and 743/742 for the asymmetric and symmetric TSP with distances one and two. More... »

PAGES

201-212

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48224-5_17

DOI

http://dx.doi.org/10.1007/3-540-48224-5_17

DIMENSIONS

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


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": "MIT Laboratory for Computer Science, 200 Technology Square, NE43-369, 02139-3594, Cambridge, Massachusetts", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Laboratory for Computer Science, 200 Technology Square, NE43-369, 02139-3594, Cambridge, Massachusetts"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Engebretsen", 
        "givenName": "Lars", 
        "id": "sg:person.010411063303.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010411063303.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Bonn, 53117, Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science, University of Bonn, 53117, Bonn"
          ], 
          "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": "2001-07-04", 
    "datePublishedReg": "2001-07-04", 
    "description": "The general asymmetric (and metric) TSP is known to be approximable only to within an O(log n) factor, and is also known to be approximable within a constant factor as soon as the metric is bounded. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics and prove approximation lower bounds of 101/100 and 203/202, respectively, for these problems. We prove also approximation lower bounds of 321/320 and 743/742 for the asymmetric and symmetric TSP with distances one and two.", 
    "editor": [
      {
        "familyName": "Orejas", 
        "givenName": "Fernando", 
        "type": "Person"
      }, 
      {
        "familyName": "Spirakis", 
        "givenName": "Paul G.", 
        "type": "Person"
      }, 
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48224-5_17", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42287-7", 
        "978-3-540-48224-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation lower bounds", 
      "lower bounds", 
      "TSP problem", 
      "constant factor", 
      "symmetric TSP problems", 
      "symmetric TSP", 
      "approximation hardness", 
      "asymmetric TSP", 
      "bounds", 
      "distance one", 
      "problem", 
      "TSP", 
      "metrics", 
      "one", 
      "factors", 
      "hardness", 
      "paper"
    ], 
    "name": "Approximation Hardness of TSP with Bounded Metrics", 
    "pagination": "201-212", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004301916"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48224-5_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48224-5_17", 
      "https://app.dimensions.ai/details/publication/pub.1004301916"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:46", 
    "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_132.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48224-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/3-540-48224-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/3-540-48224-5_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48224-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/3-540-48224-5_17'


 

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

96 TRIPLES      22 PREDICATES      41 URIs      34 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48224-5_17 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Ndd52a1e26b9540a9ae32917d9e645919
4 schema:datePublished 2001-07-04
5 schema:datePublishedReg 2001-07-04
6 schema:description The general asymmetric (and metric) TSP is known to be approximable only to within an O(log n) factor, and is also known to be approximable within a constant factor as soon as the metric is bounded. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics and prove approximation lower bounds of 101/100 and 203/202, respectively, for these problems. We prove also approximation lower bounds of 321/320 and 743/742 for the asymmetric and symmetric TSP with distances one and two.
7 schema:editor N85962342dc424ba19511a949d275da8d
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N2440a8188123419a93eed546e5a5d0c4
11 schema:keywords TSP
12 TSP problem
13 approximation hardness
14 approximation lower bounds
15 asymmetric TSP
16 bounds
17 constant factor
18 distance one
19 factors
20 hardness
21 lower bounds
22 metrics
23 one
24 paper
25 problem
26 symmetric TSP
27 symmetric TSP problems
28 schema:name Approximation Hardness of TSP with Bounded Metrics
29 schema:pagination 201-212
30 schema:productId N2d39841ef13f4e45b606d475dd2b867d
31 Nfa61793681e248b88e31a73ce9644085
32 schema:publisher N83f1484e668f46a68543dbf78ac0e550
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004301916
34 https://doi.org/10.1007/3-540-48224-5_17
35 schema:sdDatePublished 2022-12-01T06:46
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher Na3db240b2b514aa6953defd17c183960
38 schema:url https://doi.org/10.1007/3-540-48224-5_17
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N04841c8444834e7bb21078dcd1b35487 rdf:first N406bc591a99a489e8af38d5efda2dd46
43 rdf:rest rdf:nil
44 N2440a8188123419a93eed546e5a5d0c4 schema:isbn 978-3-540-42287-7
45 978-3-540-48224-6
46 schema:name Automata, Languages and Programming
47 rdf:type schema:Book
48 N2d39841ef13f4e45b606d475dd2b867d schema:name doi
49 schema:value 10.1007/3-540-48224-5_17
50 rdf:type schema:PropertyValue
51 N3615fe3f7d9d44b0ae1e556f2aff0090 rdf:first sg:person.011636042271.02
52 rdf:rest rdf:nil
53 N389c621036314f449a30b36d2d227114 schema:familyName Spirakis
54 schema:givenName Paul G.
55 rdf:type schema:Person
56 N406bc591a99a489e8af38d5efda2dd46 schema:familyName van Leeuwen
57 schema:givenName Jan
58 rdf:type schema:Person
59 N4457ba9aae174e5ba34f4d85549887e4 rdf:first N389c621036314f449a30b36d2d227114
60 rdf:rest N04841c8444834e7bb21078dcd1b35487
61 N83f1484e668f46a68543dbf78ac0e550 schema:name Springer Nature
62 rdf:type schema:Organisation
63 N85962342dc424ba19511a949d275da8d rdf:first Nb01d6ec2b01047fa960e693bced65f39
64 rdf:rest N4457ba9aae174e5ba34f4d85549887e4
65 Na3db240b2b514aa6953defd17c183960 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Nb01d6ec2b01047fa960e693bced65f39 schema:familyName Orejas
68 schema:givenName Fernando
69 rdf:type schema:Person
70 Ndd52a1e26b9540a9ae32917d9e645919 rdf:first sg:person.010411063303.00
71 rdf:rest N3615fe3f7d9d44b0ae1e556f2aff0090
72 Nfa61793681e248b88e31a73ce9644085 schema:name dimensions_id
73 schema:value pub.1004301916
74 rdf:type schema:PropertyValue
75 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
76 schema:name Mathematical Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
79 schema:name Applied Mathematics
80 rdf:type schema:DefinedTerm
81 sg:person.010411063303.00 schema:affiliation grid-institutes:grid.116068.8
82 schema:familyName Engebretsen
83 schema:givenName Lars
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010411063303.00
85 rdf:type schema:Person
86 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
87 schema:familyName Karpinski
88 schema:givenName Marek
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
90 rdf:type schema:Person
91 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, 53117, Bonn
92 schema:name Department of Computer Science, University of Bonn, 53117, Bonn
93 rdf:type schema:Organization
94 grid-institutes:grid.116068.8 schema:alternateName MIT Laboratory for Computer Science, 200 Technology Square, NE43-369, 02139-3594, Cambridge, Massachusetts
95 schema:name MIT Laboratory for Computer Science, 200 Technology Square, NE43-369, 02139-3594, Cambridge, Massachusetts
96 rdf:type schema:Organization
 




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


...