{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:39Z","timestamp":1750307799649,"version":"3.41.0"},"reference-count":19,"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            colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal\/unequal color comparisons of elements. We prove that (\n            <jats:italic>c<\/jats:italic>\n            \u2212 1)(\n            <jats:italic>n<\/jats:italic>\n            \u2212\n            <jats:italic>c<\/jats:italic>\n            )\/2 color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring (0.775\n            <jats:italic>c<\/jats:italic>\n            + 5.9)\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>c<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) color comparisons for\n            <jats:italic>c<\/jats:italic>\n            \u2265 9.\n          <\/jats:p>","DOI":"10.1145\/1367064.1367066","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T12:09:19Z","timestamp":1215000559000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Determining plurality"],"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","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00186-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.035"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.11.013"},{"key":"e_1_2_1_4_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_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367067"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90135-V"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794275914"},{"key":"e_1_2_1_8_1","first-page":"209","article-title":"Problem 81-6","volume":"2","author":"Blecher P.","year":"1981","unstructured":"Blecher , P. 1981 . Problem 81-6 . J. Algorithms 2 , 209 . Blecher, P. 1981. Problem 81-6. J. Algorithms 2, 209.","journal-title":"J. Algorithms"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958119.2958222"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_17"},{"key":"e_1_2_1_11_1","first-page":"376","article-title":"Solution to problem 81-5","volume":"3","author":"Fischer M. J.","year":"1982","unstructured":"Fischer , M. J. , and Salzberg , S. L. 1982 . Solution to problem 81-5 . J. Algorithms 3 , 376 -- 379 . Fischer, M. J., and Salzberg, S. L. 1982. Solution to problem 81-5. J. Algorithms 3, 376--379.","journal-title":"J. Algorithms"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Greene D. H. and Knuth D. E. 1990. Mathematics for the Analysis of Algorithms 3rd ed. Birkh\u00e4user Boston MA.   Greene D. H. and Knuth D. E. 1990. Mathematics for the Analysis of Algorithms 3rd ed. Birkh\u00e4user Boston MA.","DOI":"10.1007\/978-0-8176-4729-2"},{"key":"e_1_2_1_13_1","volume-title":"Tech. Rep. KAM-DIMATIA Series 2005-722 and ITI Series 2005-238","author":"Kral D.","year":"2005","unstructured":"Kral , D. , Sgall , J. , and Tich\u00fd , T . 2005 . Randomized strategies for the plurality problem. Tech. Rep. KAM-DIMATIA Series 2005-722 and ITI Series 2005-238 , Charles University, Prague, Czech Republic . Kral, D., Sgall, J., and Tich\u00fd, T. 2005. Randomized strategies for the plurality problem. Tech. Rep. KAM-DIMATIA Series 2005-722 and ITI Series 2005-238, Charles University, Prague, Czech Republic."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90022-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1967.264748"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275672"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.004"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(01)00142-2"},{"key":"e_1_2_1_19_1","first-page":"379","article-title":"Partial solution to problem 81-6","volume":"3","author":"Wu P. Y.","year":"1982","unstructured":"Wu , P. Y. 1982 . Partial solution to problem 81-6 . J. Algorithms 3 , 379 -- 380 . Wu, P. Y. 1982. Partial solution to problem 81-6. J. Algorithms 3, 379--380.","journal-title":"J. Algorithms"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367066","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1367064.1367066","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.1367066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1367064.1367066"],"URL":"https:\/\/doi.org\/10.1145\/1367064.1367066","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-02-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"}}]}}