Approximating the Distortion View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Alexander Hall , Christos Papadimitriou

ABSTRACT

Kenyon et al. (STOC 04) compute the distortion between one-dimensional finite point sets when the distortion is small; Papadimitriou and Safra (SODA 05) show that the problem is NP-hard to approximate within a factor of 3, albeit in 3 dimensions. We solve an open problem in these two papers by demonstrating that, when the distortion is large, it is hard to approximate within large factors, even for 1-dimensional point sets. We also introduce additive distortion, and show that it can be easily approximated within a factor of two. More... »

PAGES

111-122

Book

TITLE

Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-540-28239-6
978-3-540-31874-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11538462_10

DOI

http://dx.doi.org/10.1007/11538462_10

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "ETH Z\u00fcrich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "ETH Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hall", 
        "givenName": "Alexander", 
        "id": "sg:person.016633162116.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016633162116.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Kenyon et al.\u00a0(STOC 04) compute the distortion between one-dimensional finite point sets when the distortion is small; Papadimitriou and Safra (SODA 05) show that the problem is NP-hard to approximate within a factor of 3, albeit in 3 dimensions. We solve an open problem in these two papers by demonstrating that, when the distortion is large, it is hard to approximate within large factors, even for 1-dimensional point sets. We also introduce additive distortion, and show that it can be easily approximated within a factor of two.", 
    "editor": [
      {
        "familyName": "Chekuri", 
        "givenName": "Chandra", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11538462_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-28239-6", 
        "978-3-540-31874-3"
      ], 
      "name": "Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "factors", 
      "problem", 
      "large factor", 
      "dimensions", 
      "set", 
      "NP", 
      "distortion", 
      "Safra", 
      "paper", 
      "finite point sets", 
      "point sets", 
      "open problem", 
      "additive distortion", 
      "Papadimitriou", 
      "one-dimensional finite point sets"
    ], 
    "name": "Approximating the Distortion", 
    "pagination": "111-122", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030231474"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11538462_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11538462_10", 
      "https://app.dimensions.ai/details/publication/pub.1030231474"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_30.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11538462_10"
  }
]
 

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/11538462_10'

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/11538462_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11538462_10'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11538462_10'


 

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

100 TRIPLES      23 PREDICATES      41 URIs      34 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11538462_10 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb57a66d1361c48648245c9cbf897d77b
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description Kenyon et al. (STOC 04) compute the distortion between one-dimensional finite point sets when the distortion is small; Papadimitriou and Safra (SODA 05) show that the problem is NP-hard to approximate within a factor of 3, albeit in 3 dimensions. We solve an open problem in these two papers by demonstrating that, when the distortion is large, it is hard to approximate within large factors, even for 1-dimensional point sets. We also introduce additive distortion, and show that it can be easily approximated within a factor of two.
7 schema:editor N1fb7ede0c2a94392981bb0578b818efb
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N56bb2d371f594cb99497db0ef613f364
12 schema:keywords NP
13 Papadimitriou
14 Safra
15 additive distortion
16 dimensions
17 distortion
18 factors
19 finite point sets
20 large factor
21 one-dimensional finite point sets
22 open problem
23 paper
24 point sets
25 problem
26 set
27 schema:name Approximating the Distortion
28 schema:pagination 111-122
29 schema:productId N492adeef8f3f44c19ed15ae6908d9544
30 N7b20803e751c4352aa150284dec2f095
31 schema:publisher N7778fe137eb749038e5f1d75d6b64244
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030231474
33 https://doi.org/10.1007/11538462_10
34 schema:sdDatePublished 2021-12-01T20:04
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N95d747353df14b4ab1a4defe5e627463
37 schema:url https://doi.org/10.1007/11538462_10
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N1fb7ede0c2a94392981bb0578b818efb rdf:first Ncf7e8744bdd240df934be63746c15595
42 rdf:rest N557459dd481f40e4998d1aabef33db57
43 N492adeef8f3f44c19ed15ae6908d9544 schema:name doi
44 schema:value 10.1007/11538462_10
45 rdf:type schema:PropertyValue
46 N557459dd481f40e4998d1aabef33db57 rdf:first Nae5430a6b41746ae9f36ebd83860daa8
47 rdf:rest N6acd1830d6b345ad9aee182e664e120d
48 N56bb2d371f594cb99497db0ef613f364 schema:isbn 978-3-540-28239-6
49 978-3-540-31874-3
50 schema:name Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
51 rdf:type schema:Book
52 N655998c2ddc14a58bcf44c75d318294e rdf:first N96c3f8ba6d484e95ab859c64355b828c
53 rdf:rest rdf:nil
54 N6acd1830d6b345ad9aee182e664e120d rdf:first Nec3d5c9fc5b7476297313698fb704871
55 rdf:rest N655998c2ddc14a58bcf44c75d318294e
56 N7778fe137eb749038e5f1d75d6b64244 schema:name Springer Nature
57 rdf:type schema:Organisation
58 N7b20803e751c4352aa150284dec2f095 schema:name dimensions_id
59 schema:value pub.1030231474
60 rdf:type schema:PropertyValue
61 N7cb2cc1c4541424989eaf8663a11ef7f rdf:first sg:person.013233165465.63
62 rdf:rest rdf:nil
63 N95d747353df14b4ab1a4defe5e627463 schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 N96c3f8ba6d484e95ab859c64355b828c schema:familyName Trevisan
66 schema:givenName Luca
67 rdf:type schema:Person
68 Nae5430a6b41746ae9f36ebd83860daa8 schema:familyName Jansen
69 schema:givenName Klaus
70 rdf:type schema:Person
71 Nb57a66d1361c48648245c9cbf897d77b rdf:first sg:person.016633162116.73
72 rdf:rest N7cb2cc1c4541424989eaf8663a11ef7f
73 Ncf7e8744bdd240df934be63746c15595 schema:familyName Chekuri
74 schema:givenName Chandra
75 rdf:type schema:Person
76 Nec3d5c9fc5b7476297313698fb704871 schema:familyName Rolim
77 schema:givenName José D. P.
78 rdf:type schema:Person
79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
80 schema:name Information and Computing Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
83 schema:name Computation Theory and Mathematics
84 rdf:type schema:DefinedTerm
85 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
86 schema:familyName Papadimitriou
87 schema:givenName Christos
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
89 rdf:type schema:Person
90 sg:person.016633162116.73 schema:affiliation grid-institutes:grid.5801.c
91 schema:familyName Hall
92 schema:givenName Alexander
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016633162116.73
94 rdf:type schema:Person
95 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley, USA
96 schema:name UC Berkeley, USA
97 rdf:type schema:Organization
98 grid-institutes:grid.5801.c schema:alternateName ETH Zürich, Switzerland
99 schema:name ETH Zürich, Switzerland
100 rdf:type schema:Organization
 




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


...