Three Optimal Algorithms for Balls of Three Colors View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Zdeněk Dvořák , Vít Jelínek , Daniel Král’ , Jan Kynčl , Michael Saks

ABSTRACT

We consider a game played by two players, Paul and Carol. Carol fixes a coloring of n balls with three colors. At each step, Paul chooses a pair of balls and asks Carol whether the balls have the same color. Carol truthfully answers yes or no. In the Plurality problem, Paul wants to find a ball with the most common color. In the Partition problem, Paul wants to partition the balls according to their colors. He wants to ask Carol the least number of questions to reach his goal. We find optimal deterministic and probabilistic strategies for the Partition problem and an asymptotically optimal probabilistic strategy for the Plurality problem. More... »

PAGES

206-217

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-31856-9_17

DOI

http://dx.doi.org/10.1007/978-3-540-31856-9_17

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of\u00a0Applied Mathematics and Institute for\u00a0Theoretical Computer Science (ITI), Charles University, Malostransk\u00e9 n\u00e1m\u011bst\u00ed\u00a025, 118\u00a000, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Department of\u00a0Applied Mathematics and Institute for\u00a0Theoretical Computer Science (ITI), Charles University, Malostransk\u00e9 n\u00e1m\u011bst\u00ed\u00a025, 118\u00a000, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dvo\u0159\u00e1k", 
        "givenName": "Zden\u011bk", 
        "id": "sg:person.016201177201.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016201177201.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of\u00a0Applied Mathematics and Institute for\u00a0Theoretical Computer Science (ITI), Charles University, Malostransk\u00e9 n\u00e1m\u011bst\u00ed\u00a025, 118\u00a000, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Department of\u00a0Applied Mathematics and Institute for\u00a0Theoretical Computer Science (ITI), Charles University, Malostransk\u00e9 n\u00e1m\u011bst\u00ed\u00a025, 118\u00a000, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jel\u00ednek", 
        "givenName": "V\u00edt", 
        "id": "sg:person.011151456640.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011151456640.77"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of\u00a0Applied Mathematics and Institute for\u00a0Theoretical Computer Science (ITI), Charles University, Malostransk\u00e9 n\u00e1m\u011bst\u00ed\u00a025, 118\u00a000, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Department of\u00a0Applied Mathematics and Institute for\u00a0Theoretical Computer Science (ITI), Charles University, Malostransk\u00e9 n\u00e1m\u011bst\u00ed\u00a025, 118\u00a000, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kr\u00e1l\u2019", 
        "givenName": "Daniel", 
        "id": "sg:person.012161533423.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012161533423.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of\u00a0Applied Mathematics and Institute for\u00a0Theoretical Computer Science (ITI), Charles University, Malostransk\u00e9 n\u00e1m\u011bst\u00ed\u00a025, 118\u00a000, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Department of\u00a0Applied Mathematics and Institute for\u00a0Theoretical Computer Science (ITI), Charles University, Malostransk\u00e9 n\u00e1m\u011bst\u00ed\u00a025, 118\u00a000, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kyn\u010dl", 
        "givenName": "Jan", 
        "id": "sg:person.07374244226.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07374244226.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers, the State University of NJ, 110 Frelinghuysen Road, 08854-8019, Piscataway, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers, the State University of NJ, 110 Frelinghuysen Road, 08854-8019, Piscataway, 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": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We consider a game played by two players, Paul and Carol. Carol fixes a coloring of n balls with three colors. At each step, Paul chooses a pair of balls and asks Carol whether the balls have the same color. Carol truthfully answers yes or no. In the Plurality problem, Paul wants to find a ball with the most common color. In the Partition problem, Paul wants to partition the balls according to their colors. He wants to ask Carol the least number of questions to reach his goal. We find optimal deterministic and probabilistic strategies for the Partition problem and an asymptotically optimal probabilistic strategy for the Plurality problem.", 
    "editor": [
      {
        "familyName": "Diekert", 
        "givenName": "Volker", 
        "type": "Person"
      }, 
      {
        "familyName": "Durand", 
        "givenName": "Bruno", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-31856-9_17", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24998-6", 
        "978-3-540-31856-9"
      ], 
      "name": "STACS 2005", 
      "type": "Book"
    }, 
    "keywords": [
      "partition problem", 
      "probabilistic strategy", 
      "optimal algorithm", 
      "least number", 
      "game", 
      "same color", 
      "Plurality problem", 
      "algorithm", 
      "Carol", 
      "coloring", 
      "color", 
      "common color", 
      "goal", 
      "players", 
      "step", 
      "pair of balls", 
      "number", 
      "strategies", 
      "n balls", 
      "ball", 
      "pairs", 
      "questions", 
      "problem", 
      "Paul"
    ], 
    "name": "Three Optimal Algorithms for Balls of Three Colors", 
    "pagination": "206-217", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032620341"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-31856-9_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-31856-9_17", 
      "https://app.dimensions.ai/details/publication/pub.1032620341"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_319.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-31856-9_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/978-3-540-31856-9_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/978-3-540-31856-9_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-31856-9_17'

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-540-31856-9_17'


 

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

119 TRIPLES      22 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-31856-9_17 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N0812c755d38a4b24a3fbe74fce8f9d1b
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description We consider a game played by two players, Paul and Carol. Carol fixes a coloring of n balls with three colors. At each step, Paul chooses a pair of balls and asks Carol whether the balls have the same color. Carol truthfully answers yes or no. In the Plurality problem, Paul wants to find a ball with the most common color. In the Partition problem, Paul wants to partition the balls according to their colors. He wants to ask Carol the least number of questions to reach his goal. We find optimal deterministic and probabilistic strategies for the Partition problem and an asymptotically optimal probabilistic strategy for the Plurality problem.
7 schema:editor Nd4845d4ec85d4bff871831a937a1906f
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nd6fff071894241198f82b6d0d39f041d
11 schema:keywords Carol
12 Paul
13 Plurality problem
14 algorithm
15 ball
16 color
17 coloring
18 common color
19 game
20 goal
21 least number
22 n balls
23 number
24 optimal algorithm
25 pair of balls
26 pairs
27 partition problem
28 players
29 probabilistic strategy
30 problem
31 questions
32 same color
33 step
34 strategies
35 schema:name Three Optimal Algorithms for Balls of Three Colors
36 schema:pagination 206-217
37 schema:productId N029c8952a6914460b0fb046dd7602e5b
38 Ne6d7a951b91e44e9ae2c3f11de940c8e
39 schema:publisher Nf342ea99866b4574ac6b2483bd6bed6b
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032620341
41 https://doi.org/10.1007/978-3-540-31856-9_17
42 schema:sdDatePublished 2022-09-02T16:14
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Na36c65cb8c7949958a62464554c73b2f
45 schema:url https://doi.org/10.1007/978-3-540-31856-9_17
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N029c8952a6914460b0fb046dd7602e5b schema:name dimensions_id
50 schema:value pub.1032620341
51 rdf:type schema:PropertyValue
52 N057bbf62881246c4a4892841e832b3ed rdf:first sg:person.011151456640.77
53 rdf:rest N3e3ccef1bc204483befde1c440a3b008
54 N0812c755d38a4b24a3fbe74fce8f9d1b rdf:first sg:person.016201177201.22
55 rdf:rest N057bbf62881246c4a4892841e832b3ed
56 N3e3ccef1bc204483befde1c440a3b008 rdf:first sg:person.012161533423.79
57 rdf:rest N70b4ab5dbc6346bea04fd42e324474fb
58 N70b4ab5dbc6346bea04fd42e324474fb rdf:first sg:person.07374244226.25
59 rdf:rest N951f62a948ef4e9889427d6ebc62ecee
60 N951f62a948ef4e9889427d6ebc62ecee rdf:first sg:person.011520224512.05
61 rdf:rest rdf:nil
62 Na36c65cb8c7949958a62464554c73b2f schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 Naed57bcc062b42579aec2d0123c9d021 rdf:first Nb13a7727b56a41d5a34ab27b1790e4da
65 rdf:rest rdf:nil
66 Nb13a7727b56a41d5a34ab27b1790e4da schema:familyName Durand
67 schema:givenName Bruno
68 rdf:type schema:Person
69 Nd3b590995609436d800d900d9788774e schema:familyName Diekert
70 schema:givenName Volker
71 rdf:type schema:Person
72 Nd4845d4ec85d4bff871831a937a1906f rdf:first Nd3b590995609436d800d900d9788774e
73 rdf:rest Naed57bcc062b42579aec2d0123c9d021
74 Nd6fff071894241198f82b6d0d39f041d schema:isbn 978-3-540-24998-6
75 978-3-540-31856-9
76 schema:name STACS 2005
77 rdf:type schema:Book
78 Ne6d7a951b91e44e9ae2c3f11de940c8e schema:name doi
79 schema:value 10.1007/978-3-540-31856-9_17
80 rdf:type schema:PropertyValue
81 Nf342ea99866b4574ac6b2483bd6bed6b schema:name Springer Nature
82 rdf:type schema:Organisation
83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
84 schema:name Information and Computing Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
87 schema:name Artificial Intelligence and Image Processing
88 rdf:type schema:DefinedTerm
89 sg:person.011151456640.77 schema:affiliation grid-institutes:grid.4491.8
90 schema:familyName Jelínek
91 schema:givenName Vít
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011151456640.77
93 rdf:type schema:Person
94 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
95 schema:familyName Saks
96 schema:givenName Michael
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
98 rdf:type schema:Person
99 sg:person.012161533423.79 schema:affiliation grid-institutes:grid.4491.8
100 schema:familyName Král’
101 schema:givenName Daniel
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012161533423.79
103 rdf:type schema:Person
104 sg:person.016201177201.22 schema:affiliation grid-institutes:grid.4491.8
105 schema:familyName Dvořák
106 schema:givenName Zdeněk
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016201177201.22
108 rdf:type schema:Person
109 sg:person.07374244226.25 schema:affiliation grid-institutes:grid.4491.8
110 schema:familyName Kynčl
111 schema:givenName Jan
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07374244226.25
113 rdf:type schema:Person
114 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers, the State University of NJ, 110 Frelinghuysen Road, 08854-8019, Piscataway, NJ, USA
115 schema:name Department of Mathematics, Rutgers, the State University of NJ, 110 Frelinghuysen Road, 08854-8019, Piscataway, NJ, USA
116 rdf:type schema:Organization
117 grid-institutes:grid.4491.8 schema:alternateName Department of Applied Mathematics and Institute for Theoretical Computer Science (ITI), Charles University, Malostranské náměstí 25, 118 00, Prague, Czech Republic
118 schema:name Department of Applied Mathematics and Institute for Theoretical Computer Science (ITI), Charles University, Malostranské náměstí 25, 118 00, Prague, Czech Republic
119 rdf:type schema:Organization
 




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


...