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-12-01T06:53", 
    "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_400.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 Na7de9c284d0e44caa006e58e887812d2
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 N5f49db8f57bf460eb9ce6b629bc2ec27
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N3782f1381fc84ce995472ee7416892cd
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 N91a76e060b704d298376d2ee24425563
38 Nb0d9c73ebd754534871af90622d8139d
39 schema:publisher Nac1d19ebfd1c420e8a7a502dc836426c
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-12-01T06:53
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Nda1f41d8ffd84b1a962e42508ae730c3
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 N044a9bd29e2647d0b74564e57fffb0ad rdf:first Nfd80f084c40e4c349143918d09429592
50 rdf:rest rdf:nil
51 N049d77340e6841a9869502ca7f7d29d5 schema:familyName Diekert
52 schema:givenName Volker
53 rdf:type schema:Person
54 N152bc20b6a9e42d89ece7b4bd1438e46 rdf:first sg:person.07374244226.25
55 rdf:rest N4a2291b8d52e4afd9a2479852dc6bfbe
56 N3782f1381fc84ce995472ee7416892cd schema:isbn 978-3-540-24998-6
57 978-3-540-31856-9
58 schema:name STACS 2005
59 rdf:type schema:Book
60 N4a2291b8d52e4afd9a2479852dc6bfbe rdf:first sg:person.011520224512.05
61 rdf:rest rdf:nil
62 N4e92956827cb409197e1b16079032df3 rdf:first sg:person.011151456640.77
63 rdf:rest N5cb33ad42f374ec99feb0f2009442f70
64 N5cb33ad42f374ec99feb0f2009442f70 rdf:first sg:person.012161533423.79
65 rdf:rest N152bc20b6a9e42d89ece7b4bd1438e46
66 N5f49db8f57bf460eb9ce6b629bc2ec27 rdf:first N049d77340e6841a9869502ca7f7d29d5
67 rdf:rest N044a9bd29e2647d0b74564e57fffb0ad
68 N91a76e060b704d298376d2ee24425563 schema:name doi
69 schema:value 10.1007/978-3-540-31856-9_17
70 rdf:type schema:PropertyValue
71 Na7de9c284d0e44caa006e58e887812d2 rdf:first sg:person.016201177201.22
72 rdf:rest N4e92956827cb409197e1b16079032df3
73 Nac1d19ebfd1c420e8a7a502dc836426c schema:name Springer Nature
74 rdf:type schema:Organisation
75 Nb0d9c73ebd754534871af90622d8139d schema:name dimensions_id
76 schema:value pub.1032620341
77 rdf:type schema:PropertyValue
78 Nda1f41d8ffd84b1a962e42508ae730c3 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 Nfd80f084c40e4c349143918d09429592 schema:familyName Durand
81 schema:givenName Bruno
82 rdf:type schema:Person
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)


...