Tolerant Algorithms View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Rolf Klein , Rainer Penninger , Christian Sohler , David P. Woodruff

ABSTRACT

Assume we are interested in solving a computational task, e.g., sorting n numbers, and we only have access to an unreliable primitive operation, for example, comparison between two numbers. Suppose that each primitive operation fails with probability at most p and that repeating it is not helpful, as it will result in the same outcome. Can we still approximately solve our task with probability 1 − f(p) for a function f that goes to 0 as p goes to 0? While previous work studied sorting in this model, we believe this model is also relevant for other problems. We find the maximum of n numbers in O(n) time,solve 2D linear programming in O(n logn) time,approximately sort n numbers in O(n2) time such that each number’s position deviates from its true rank by at most O(logn) positions,find an element in a sorted array in O(logn loglogn) time. Our sorting result can be seen as an alternative to a previous result of Braverman and Mossel (SODA, 2008) who employed the same model. While we do not construct the maximum likelihood permutation, we achieve similar accuracy with a substantially faster running time. More... »

PAGES

736-747

Book

TITLE

Algorithms – ESA 2011

ISBN

978-3-642-23718-8
978-3-642-23719-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-23719-5_62

DOI

http://dx.doi.org/10.1007/978-3-642-23719-5_62

DIMENSIONS

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


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": "University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Klein", 
        "givenName": "Rolf", 
        "id": "sg:person.016501524164.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016501524164.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Penninger", 
        "givenName": "Rainer", 
        "id": "sg:person.015402164016.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015402164016.29"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "TU Dortmund, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5675.1", 
          "name": [
            "TU Dortmund, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sohler", 
        "givenName": "Christian", 
        "id": "sg:person.015650257025.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015650257025.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research-Almaden, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Research-Almaden, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David P.", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "Assume we are interested in solving a computational task, e.g., sorting n numbers, and we only have access to an unreliable primitive operation, for example, comparison between two numbers. Suppose that each primitive operation fails with probability at most p and that repeating it is not helpful, as it will result in the same outcome. Can we still approximately solve our task with probability 1\u2009\u2212\u2009f(p) for a function f that goes to 0 as p goes to 0? While previous work studied sorting in this model, we believe this model is also relevant for other problems. We \nfind the maximum of n numbers in O(n) time,solve 2D linear programming in O(n logn) time,approximately sort n numbers in O(n2) time such that each number\u2019s position deviates from its true rank by at most O(logn) positions,find an element in a sorted array in O(logn loglogn) time.\nOur sorting result can be seen as an alternative to a previous result of Braverman and Mossel (SODA, 2008) who employed the same model. While we do not construct the maximum likelihood permutation, we achieve similar accuracy with a substantially faster running time.", 
    "editor": [
      {
        "familyName": "Demetrescu", 
        "givenName": "Camil", 
        "type": "Person"
      }, 
      {
        "familyName": "Halld\u00f3rsson", 
        "givenName": "Magn\u00fas M.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-23719-5_62", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-23718-8", 
        "978-3-642-23719-5"
      ], 
      "name": "Algorithms \u2013 ESA 2011", 
      "type": "Book"
    }, 
    "keywords": [
      "n numbers", 
      "probability 1", 
      "true rank", 
      "faster running time", 
      "linear programming", 
      "primitive operations", 
      "function f", 
      "running time", 
      "computational tasks", 
      "number position", 
      "previous results", 
      "similar accuracy", 
      "tolerant algorithm", 
      "same model", 
      "sorted array", 
      "Mossel", 
      "previous work", 
      "model", 
      "task", 
      "algorithm", 
      "Braverman", 
      "permutations", 
      "number", 
      "probability", 
      "programming", 
      "problem", 
      "rank", 
      "accuracy", 
      "operation", 
      "position", 
      "results", 
      "time", 
      "array", 
      "maximum", 
      "access", 
      "work", 
      "comparison", 
      "elements", 
      "example", 
      "alternative", 
      "same outcome", 
      "outcomes"
    ], 
    "name": "Tolerant Algorithms", 
    "pagination": "736-747", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046667531"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-23719-5_62"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-23719-5_62", 
      "https://app.dimensions.ai/details/publication/pub.1046667531"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:47", 
    "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_171.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-23719-5_62"
  }
]
 

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-23719-5_62'

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-23719-5_62'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-23719-5_62'

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-23719-5_62'


 

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

133 TRIPLES      22 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-23719-5_62 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Naf73b306b9de4951b318db3bb7afa619
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Assume we are interested in solving a computational task, e.g., sorting n numbers, and we only have access to an unreliable primitive operation, for example, comparison between two numbers. Suppose that each primitive operation fails with probability at most p and that repeating it is not helpful, as it will result in the same outcome. Can we still approximately solve our task with probability 1 − f(p) for a function f that goes to 0 as p goes to 0? While previous work studied sorting in this model, we believe this model is also relevant for other problems. We find the maximum of n numbers in O(n) time,solve 2D linear programming in O(n logn) time,approximately sort n numbers in O(n2) time such that each number’s position deviates from its true rank by at most O(logn) positions,find an element in a sorted array in O(logn loglogn) time. Our sorting result can be seen as an alternative to a previous result of Braverman and Mossel (SODA, 2008) who employed the same model. While we do not construct the maximum likelihood permutation, we achieve similar accuracy with a substantially faster running time.
7 schema:editor Ndeb191f164ab46699462b3f0a5a8350a
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Neef7dcb0941c474b9e13e2a90ad31009
11 schema:keywords Braverman
12 Mossel
13 access
14 accuracy
15 algorithm
16 alternative
17 array
18 comparison
19 computational tasks
20 elements
21 example
22 faster running time
23 function f
24 linear programming
25 maximum
26 model
27 n numbers
28 number
29 number position
30 operation
31 outcomes
32 permutations
33 position
34 previous results
35 previous work
36 primitive operations
37 probability
38 probability 1
39 problem
40 programming
41 rank
42 results
43 running time
44 same model
45 same outcome
46 similar accuracy
47 sorted array
48 task
49 time
50 tolerant algorithm
51 true rank
52 work
53 schema:name Tolerant Algorithms
54 schema:pagination 736-747
55 schema:productId N070fecd31d11466ca062a2863d6bfb1e
56 N835d999122cd4955991e427bf7d3aae0
57 schema:publisher N390a3456db0c4cfe982af0248751a23e
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046667531
59 https://doi.org/10.1007/978-3-642-23719-5_62
60 schema:sdDatePublished 2022-12-01T06:47
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher Na3cbd7b66cff4bb5a5e6d6d7c4327c30
63 schema:url https://doi.org/10.1007/978-3-642-23719-5_62
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N070fecd31d11466ca062a2863d6bfb1e schema:name doi
68 schema:value 10.1007/978-3-642-23719-5_62
69 rdf:type schema:PropertyValue
70 N390a3456db0c4cfe982af0248751a23e schema:name Springer Nature
71 rdf:type schema:Organisation
72 N3b8b1e819fe14fed81b63e37efb4d2bf schema:familyName Demetrescu
73 schema:givenName Camil
74 rdf:type schema:Person
75 N599cec7c04524f7c9cb88b5e3394313b rdf:first sg:person.015402164016.29
76 rdf:rest Nc49dc83e9b2e410b8090a00ead8ca747
77 N6982346d4f984c23b1677a1c8e8093a1 rdf:first Ne4d078ecef1f4e46b9764d8b20bf74a7
78 rdf:rest rdf:nil
79 N6d85aaa338c547bea4c9e5291848fe21 rdf:first sg:person.012727410605.86
80 rdf:rest rdf:nil
81 N835d999122cd4955991e427bf7d3aae0 schema:name dimensions_id
82 schema:value pub.1046667531
83 rdf:type schema:PropertyValue
84 Na3cbd7b66cff4bb5a5e6d6d7c4327c30 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 Naf73b306b9de4951b318db3bb7afa619 rdf:first sg:person.016501524164.01
87 rdf:rest N599cec7c04524f7c9cb88b5e3394313b
88 Nc49dc83e9b2e410b8090a00ead8ca747 rdf:first sg:person.015650257025.27
89 rdf:rest N6d85aaa338c547bea4c9e5291848fe21
90 Ndeb191f164ab46699462b3f0a5a8350a rdf:first N3b8b1e819fe14fed81b63e37efb4d2bf
91 rdf:rest N6982346d4f984c23b1677a1c8e8093a1
92 Ne4d078ecef1f4e46b9764d8b20bf74a7 schema:familyName Halldórsson
93 schema:givenName Magnús M.
94 rdf:type schema:Person
95 Neef7dcb0941c474b9e13e2a90ad31009 schema:isbn 978-3-642-23718-8
96 978-3-642-23719-5
97 schema:name Algorithms – ESA 2011
98 rdf:type schema:Book
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computation Theory and Mathematics
104 rdf:type schema:DefinedTerm
105 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
106 schema:familyName Woodruff
107 schema:givenName David P.
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
109 rdf:type schema:Person
110 sg:person.015402164016.29 schema:affiliation grid-institutes:grid.10388.32
111 schema:familyName Penninger
112 schema:givenName Rainer
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015402164016.29
114 rdf:type schema:Person
115 sg:person.015650257025.27 schema:affiliation grid-institutes:grid.5675.1
116 schema:familyName Sohler
117 schema:givenName Christian
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015650257025.27
119 rdf:type schema:Person
120 sg:person.016501524164.01 schema:affiliation grid-institutes:grid.10388.32
121 schema:familyName Klein
122 schema:givenName Rolf
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016501524164.01
124 rdf:type schema:Person
125 grid-institutes:grid.10388.32 schema:alternateName University of Bonn, Germany
126 schema:name University of Bonn, Germany
127 rdf:type schema:Organization
128 grid-institutes:grid.481551.c schema:alternateName IBM Research-Almaden, USA
129 schema:name IBM Research-Almaden, USA
130 rdf:type schema:Organization
131 grid-institutes:grid.5675.1 schema:alternateName TU Dortmund, Germany
132 schema:name TU Dortmund, Germany
133 rdf:type schema:Organization
 




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


...