{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:40Z","timestamp":1750307800104,"version":"3.41.0"},"reference-count":4,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            Given a set of\n            <jats:italic>n<\/jats:italic>\n            elements, each of which is colored one of\n            <jats:italic>c<\/jats:italic>\n            \u2265 2 colors, we have to determine an element of the plurality (most frequently occurring) color by pairwise equal\/unequal color comparisons of elements. We derive lower bounds for the expected number of color comparisons when the\n            <jats:italic>\n              c\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            colorings are equally probable. We prove a general lower bound of\n            <jats:italic>c<\/jats:italic>\n            \/3\n            <jats:italic>n<\/jats:italic>\n            \u2212\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>c<\/jats:italic>\n            \u2265 2; we prove the stronger particular bounds of 7\/6\n            <jats:italic>n<\/jats:italic>\n            \u2212\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>c<\/jats:italic>\n            = 3, 54\/35\n            <jats:italic>n<\/jats:italic>\n            \u2212\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>c<\/jats:italic>\n            = 4, 607\/315\n            <jats:italic>n<\/jats:italic>\n            \u2212\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>c<\/jats:italic>\n            = 5, 1592\/693\n            <jats:italic>n<\/jats:italic>\n            \u2212\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>c<\/jats:italic>\n            = 6, 7985\/3003\n            <jats:italic>n<\/jats:italic>\n            \u2212\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>c<\/jats:italic>\n            = 7, and 19402\/6435\n            <jats:italic>n<\/jats:italic>\n            \u2212\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) for\n            <jats:italic>c<\/jats:italic>\n            = 8.\n          <\/jats:p>","DOI":"10.1145\/1367064.1367067","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T12:09:19Z","timestamp":1215000559000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Average-case lower bounds for the plurality problem"],"prefix":"10.1145","volume":"4","author":[{"given":"Laurent","family":"Alonso","sequence":"first","affiliation":[{"name":"INRIA-Lorraine, Vandoeuvre-l\u00e8s-Nancy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edward M.","family":"Reingold","sequence":"additional","affiliation":[{"name":"Illinois Institute of Technology, Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,7,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Alonso L. and Reingold E. M. 2006. Average-case analysis of some plurality algorithms. Submitted for publication.  Alonso L. and Reingold E. M. 2006. Average-case analysis of some plurality algorithms. Submitted for publication."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367066"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90135-V"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794275914"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367067","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1367064.1367067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:30Z","timestamp":1750254990000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":4,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1367064.1367067"],"URL":"https:\/\/doi.org\/10.1145\/1367064.1367067","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2006-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}