The Information Theoretic Bound for Problems on Ordered Sets and Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1985

AUTHORS

Michael Saks

ABSTRACT

One of the most basic problems arising in computer science is to sort a set X with unknown total order. The objective is to minimize the number of steps needed in worst case, where a step consists of a comparison of two elements x and y (this comparison is denoted x:y). The result of each comparison reduces the set of possible orderings of X to one of two sets: those in which x < y and those in which y < x. Since it is possible that the larger of these two sets remains, the number of possible orders on X is reduced by no more than half. In worst case we need at least log n! = n log n + 0(n) comparisons to sort the n-element set X. (We write log for log2 throughout this paper.)This is an example of an information theoretic bound (ITB) for a combinatorial decision problem, one of the few general techniques known for obtaining lower bounds on the computational complexity of a problem. For those problems where this argument is applicable, a natural question to ask is: “can this bound be achieved?” or “how close can we come to achieving the bound?” For the sorting problem above there are several well-known algorithms that essentially attain the ITB (see [Kn]), but of course this is not the case for all such problems.This paper is a survey of a number of computational problems involving ordered sets and graphs in which the ITB can be applied. As will be seen, the derivation of these bounds and the question of how good they are often lead to combinatorial questions that are interesting in their own right. More... »

PAGES

137-168

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-94-009-5315-4_4

DOI

http://dx.doi.org/10.1007/978-94-009-5315-4_4

DIMENSIONS

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


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": "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1985", 
    "datePublishedReg": "1985-01-01", 
    "description": "One of the most basic problems arising in computer science is to sort a set X with unknown total order. The objective is to minimize the number of steps needed in worst case, where a step consists of a comparison of two elements x and y (this comparison is denoted x:y). The result of each comparison reduces the set of possible orderings of X to one of two sets: those in which x < y and those in which y < x. Since it is possible that the larger of these two sets remains, the number of possible orders on X is reduced by no more than half. In worst case we need at least log n! = n log n + 0(n) comparisons to sort the n-element set X. (We write log for log2 throughout this paper.)This is an example of an information theoretic bound (ITB) for a combinatorial decision problem, one of the few general techniques known for obtaining lower bounds on the computational complexity of a problem. For those problems where this argument is applicable, a natural question to ask is: \u201ccan this bound be achieved?\u201d or \u201chow close can we come to achieving the bound?\u201d For the sorting problem above there are several well-known algorithms that essentially attain the ITB (see [Kn]), but of course this is not the case for all such problems.This paper is a survey of a number of computational problems involving ordered sets and graphs in which the ITB can be applied. As will be seen, the derivation of these bounds and the question of how good they are often lead to combinatorial questions that are interesting in their own right.", 
    "editor": [
      {
        "familyName": "Rival", 
        "givenName": "Ivan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-94-009-5315-4_4", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-94-010-8848-0", 
        "978-94-009-5315-4"
      ], 
      "name": "Graphs and Order", 
      "type": "Book"
    }, 
    "keywords": [
      "combinatorial decision problems", 
      "information-theoretic bounds", 
      "log n", 
      "worst case", 
      "computer science", 
      "n log n", 
      "computational complexity", 
      "computational problems", 
      "information theoretic", 
      "theoretic bounds", 
      "combinatorial questions", 
      "lower bounds", 
      "Ordered Sets", 
      "sorting problem", 
      "such problems", 
      "bounds", 
      "possible order", 
      "decision problem", 
      "natural question", 
      "general technique", 
      "possible orderings", 
      "basic problem", 
      "least log n", 
      "total order", 
      "graph", 
      "number of steps", 
      "element x", 
      "set", 
      "problem", 
      "n elements", 
      "algorithm", 
      "theoretic", 
      "complexity", 
      "derivation", 
      "ordering", 
      "logs", 
      "own right", 
      "step", 
      "number", 
      "order", 
      "cases", 
      "technique", 
      "comparison", 
      "example", 
      "science", 
      "argument", 
      "questions", 
      "objective", 
      "results", 
      "log2", 
      "ITB", 
      "survey", 
      "course", 
      "rights", 
      "half", 
      "paper"
    ], 
    "name": "The Information Theoretic Bound for Problems on Ordered Sets and Graphs", 
    "pagination": "137-168", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003834460"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-94-009-5315-4_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-94-009-5315-4_4", 
      "https://app.dimensions.ai/details/publication/pub.1003834460"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_224.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-94-009-5315-4_4"
  }
]
 

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-94-009-5315-4_4'

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-94-009-5315-4_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-94-009-5315-4_4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-94-009-5315-4_4'


 

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

115 TRIPLES      22 PREDICATES      81 URIs      74 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-94-009-5315-4_4 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ne474c02890fc4469846337e130702196
4 schema:datePublished 1985
5 schema:datePublishedReg 1985-01-01
6 schema:description One of the most basic problems arising in computer science is to sort a set X with unknown total order. The objective is to minimize the number of steps needed in worst case, where a step consists of a comparison of two elements x and y (this comparison is denoted x:y). The result of each comparison reduces the set of possible orderings of X to one of two sets: those in which x < y and those in which y < x. Since it is possible that the larger of these two sets remains, the number of possible orders on X is reduced by no more than half. In worst case we need at least log n! = n log n + 0(n) comparisons to sort the n-element set X. (We write log for log2 throughout this paper.)This is an example of an information theoretic bound (ITB) for a combinatorial decision problem, one of the few general techniques known for obtaining lower bounds on the computational complexity of a problem. For those problems where this argument is applicable, a natural question to ask is: “can this bound be achieved?” or “how close can we come to achieving the bound?” For the sorting problem above there are several well-known algorithms that essentially attain the ITB (see [Kn]), but of course this is not the case for all such problems.This paper is a survey of a number of computational problems involving ordered sets and graphs in which the ITB can be applied. As will be seen, the derivation of these bounds and the question of how good they are often lead to combinatorial questions that are interesting in their own right.
7 schema:editor N828eb92d850f49008ae7d8ff44860f3e
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N7c513c85cf55476bb1c9fb76699f9af0
11 schema:keywords ITB
12 Ordered Sets
13 algorithm
14 argument
15 basic problem
16 bounds
17 cases
18 combinatorial decision problems
19 combinatorial questions
20 comparison
21 complexity
22 computational complexity
23 computational problems
24 computer science
25 course
26 decision problem
27 derivation
28 element x
29 example
30 general technique
31 graph
32 half
33 information theoretic
34 information-theoretic bounds
35 least log n
36 log n
37 log2
38 logs
39 lower bounds
40 n elements
41 n log n
42 natural question
43 number
44 number of steps
45 objective
46 order
47 ordering
48 own right
49 paper
50 possible order
51 possible orderings
52 problem
53 questions
54 results
55 rights
56 science
57 set
58 sorting problem
59 step
60 such problems
61 survey
62 technique
63 theoretic
64 theoretic bounds
65 total order
66 worst case
67 schema:name The Information Theoretic Bound for Problems on Ordered Sets and Graphs
68 schema:pagination 137-168
69 schema:productId N8effa04cfdfe4ca8aa73e4011dd25a16
70 N9d595d1b1277494196372c7c7766c7b5
71 schema:publisher Ne671a8ddfe344fceb50461d85ad63b58
72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003834460
73 https://doi.org/10.1007/978-94-009-5315-4_4
74 schema:sdDatePublished 2022-10-01T06:54
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher N9f537bb693ff4e0a9e6391907a95b951
77 schema:url https://doi.org/10.1007/978-94-009-5315-4_4
78 sgo:license sg:explorer/license/
79 sgo:sdDataset chapters
80 rdf:type schema:Chapter
81 N7c513c85cf55476bb1c9fb76699f9af0 schema:isbn 978-94-009-5315-4
82 978-94-010-8848-0
83 schema:name Graphs and Order
84 rdf:type schema:Book
85 N828eb92d850f49008ae7d8ff44860f3e rdf:first Ndb54ed8c1b364eec9d26a44b29bee1b0
86 rdf:rest rdf:nil
87 N8effa04cfdfe4ca8aa73e4011dd25a16 schema:name dimensions_id
88 schema:value pub.1003834460
89 rdf:type schema:PropertyValue
90 N9d595d1b1277494196372c7c7766c7b5 schema:name doi
91 schema:value 10.1007/978-94-009-5315-4_4
92 rdf:type schema:PropertyValue
93 N9f537bb693ff4e0a9e6391907a95b951 schema:name Springer Nature - SN SciGraph project
94 rdf:type schema:Organization
95 Ndb54ed8c1b364eec9d26a44b29bee1b0 schema:familyName Rival
96 schema:givenName Ivan
97 rdf:type schema:Person
98 Ne474c02890fc4469846337e130702196 rdf:first sg:person.011520224512.05
99 rdf:rest rdf:nil
100 Ne671a8ddfe344fceb50461d85ad63b58 schema:name Springer Nature
101 rdf:type schema:Organisation
102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
103 schema:name Information and Computing Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
106 schema:name Computation Theory and Mathematics
107 rdf:type schema:DefinedTerm
108 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
109 schema:familyName Saks
110 schema:givenName Michael
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
112 rdf:type schema:Person
113 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA
114 schema:name Department of Mathematics, Rutgers University, 08903, New Brunswick, NJ, USA
115 rdf:type schema:Organization
 




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


...