{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:56:25Z","timestamp":1725468985679},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540377917"},{"type":"electronic","value":"9783540377931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11821069_46","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T10:25:12Z","timestamp":1156501512000},"page":"528-539","source":"Crossref","is-referenced-by-count":9,"title":["Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners"],"prefix":"10.1007","author":[{"given":"Christopher M.","family":"Homan","sequence":"first","affiliation":[]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"46_CR1","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/268999.269002","volume":"44","author":"E. Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Exact analysis of Dodgson elections: Lewis Carroll\u2019s 1876 voting system is complete for parallel access to NP. Journal of the ACM\u00a044(6), 806\u2013825 (1997)","journal-title":"Journal of the ACM"},{"key":"46_CR2","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00303169","volume":"6","author":"J. Bartholdi III","year":"1989","unstructured":"Bartholdi III, J., Tovey, C., Trick, M.: Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare\u00a06, 157\u2013165 (1989)","journal-title":"Social Choice and Welfare"},{"key":"#cr-split#-46_CR3.1","unstructured":"Condorcet, M.: Essai sur l???Application de L???Analyse ?? la Probabilit?? des D??cisions Rendues ?? la Pluralit?? des Voix (1785);"},{"key":"#cr-split#-46_CR3.2","unstructured":"Facsimile reprint of original published in Paris, The Imprimerie Royale (1972)"},{"key":"46_CR4","doi-asserted-by":"crossref","DOI":"10.3998\/mpub.12736","volume-title":"Classics of Social Choice","author":"I. McLean","year":"1995","unstructured":"McLean, I., Urken, A.: Classics of Social Choice. University of Michigan Press, Ann Arbor (1995)"},{"key":"46_CR5","volume-title":"A method of taking votes on more than two issues","author":"C. Dodgson","year":"1876","unstructured":"Dodgson, C.: A method of taking votes on more than two issues. Clarendon Press, Oxford, pamphet (1876)"},{"key":"46_CR6","volume-title":"The Theory of Committees and Elections","author":"D. Black","year":"1958","unstructured":"Black, D.: The Theory of Committees and Elections. Cambridge University Press, Cambridge (1958)"},{"key":"46_CR7","first-page":"197","volume":"19","author":"E. Nanson","year":"1882","unstructured":"Nanson, E.: Methods of election. Transactions and Proceedings of the Royal Society of Victoria\u00a019, 197\u2013240 (1882)","journal-title":"Transactions and Proceedings of the Royal Society of Victoria"},{"key":"46_CR8","unstructured":"Borda, J.C.d.: M\u00e9moire sur les \u00e9lections au scrutin. Histoire de L\u2019Acad\u00e9mie Royale des Sciences Ann\u00e9e 1781 (1784)"},{"key":"46_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BFb0009651","volume-title":"Theoretical Computer Science","author":"C. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C., Zachos, S.: Two remarks on the power of counting. In: Cremers, A.B., Kriegel, H.-P. (eds.) GI-TCS 1983. LNCS, vol.\u00a0145, pp. 269\u2013276. Springer, Heidelberg (1982)"},{"issue":"3","key":"46_CR10","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.tcs.2005.08.031","volume":"349","author":"E. Hemaspaandra","year":"2005","unstructured":"Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Theoretical Computer Science\u00a0349(3), 382\u2013391 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"46_CR11","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00224-002-1093-z","volume":"36","author":"J. Rothe","year":"2003","unstructured":"Rothe, J., Spakowski, H., Vogel, J.: Exact complexity of the winner problem for Young elections. Theory of Computing Systems\u00a036(4), 375\u2013386 (2003)","journal-title":"Theory of Computing Systems"},{"key":"46_CR12","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press\/McGraw Hill (2001)"},{"issue":"1","key":"46_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"G. Ausiello","year":"1995","unstructured":"Ausiello, G., Crescenzi, P., Protasi, M.: Approximate solution of NP optimization problems. Theoretical Computer Science\u00a0150(1), 1\u201355 (1995)","journal-title":"Theoretical Computer Science"},{"key":"46_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1007\/3-540-45749-6_51","volume-title":"Algorithms - ESA 2002","author":"A.C. Kaporis","year":"2002","unstructured":"Kaporis, A.C., Kirousis, L.M., Lalas, E.G.: The probabilistic analysis of a greedy satisfiability algorithm. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 574\u2013585. Springer, Heidelberg (2002)"},{"issue":"3","key":"46_CR15","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1145\/321958.321961","volume":"23","author":"L. Chang","year":"1976","unstructured":"Chang, L., Korsh, J.: Canonical coin changing and greedy solutions. Journal of the ACM\u00a023(3), 418\u2013422 (1976)","journal-title":"Journal of the ACM"},{"key":"46_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1007\/3-540-12689-9_118","volume-title":"Foundations of Computation Theory","author":"M. Protasi","year":"1983","unstructured":"Protasi, M., Talamo, M.: A new probabilistic model for the study of algorithmic properties of random graph problems. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol.\u00a0158, pp. 360\u2013367. Springer, Heidelberg (1983)"},{"issue":"2","key":"46_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jagm.1997.0887","volume":"25","author":"P. Slavik","year":"1997","unstructured":"Slavik, P.: A tight analysis of the greedy algorithm for set cover. Journal of Algorithms\u00a025(2), 237\u2013254 (1997)","journal-title":"Journal of Algorithms"},{"key":"46_CR18","first-page":"206","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"D. Brown","year":"2001","unstructured":"Brown, D.: A probabilistic analysis of a greedy algorithm arising from computational biology. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 206\u2013207. ACM Press, New York (2001)"},{"key":"46_CR19","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., Marchetti-Spaccamela, A.: On finding the exact solution of a zero-one knapsack problem. In: Proceedings of the 16th ACM Symposium on Theory of Computing, pp. 359\u2013368 (1984)","DOI":"10.1145\/800057.808701"},{"key":"46_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized complexity. Springer, Heidelberg (1999)"},{"key":"46_CR21","doi-asserted-by":"crossref","unstructured":"Levin, L.: Average case complete problems. SIAM Journal on Computing (1986)","DOI":"10.1137\/0215020"},{"issue":"3","key":"46_CR22","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D. Spielman","year":"2004","unstructured":"Spielman, D., Teng, S.: Smoothed analysis: Why the simplex algorithm usually takes polynomial time. Journal of the ACM\u00a051(3), 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"key":"46_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/3-540-44612-5_5","volume-title":"Mathematical Foundations of Computer Science 2000","author":"E. Hemaspaandra","year":"2000","unstructured":"Hemaspaandra, E., Hemaspaandra, L.A.: Computational politics: Electoral systems. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 64\u201383. Springer, Heidelberg (2000)"},{"key":"46_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-44450-5_28","volume-title":"FST TCS 2000: Foundations of Software Technology and Theoretical Science","author":"H. Spakowski","year":"2000","unstructured":"Spakowski, H., Vogel, J.: \u03982\n                           p-completeness: A classical approach for new results. In: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol.\u00a01974, pp. 348\u2013360. Springer, Heidelberg (2000)"},{"key":"46_CR25","unstructured":"Spakowski, H., Vogel, J.: The complexity of Kemeny\u2019s voting system. In: Proceedings of the Workshop Argentino de Inform\u00e1tica Te\u00f3rica. Anales Jornadas Argentinas de Inform\u00e1tica e Investigaci\u00f3n Operativa, vol.\u00a030, pp. 157\u2013168. SADIO (2001)"},{"key":"46_CR26","unstructured":"Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Technical Report Math\/Inf\/14\/03, Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t, Jena, Germany (2003)"},{"issue":"1\u20132","key":"46_CR27","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K. Wagner","year":"1987","unstructured":"Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. Theoretical Computer Science\u00a051(1\u20132), 53\u201380 (1987)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"46_CR28","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy I: Structural properties. SIAM Journal on Computing\u00a017(6), 1232\u20131252 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"46_CR29","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1137\/0217080","volume":"17","author":"J. Kadin","year":"1988","unstructured":"Kadin, J.: The polynomial time hierarchy collapses if the boolean hierarchy collapses. SIAM Journal on Computing\u00a017(6), 1263\u20131282 (1988); Erratum appears in the same journal, 20(2), 404","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"46_CR30","doi-asserted-by":"crossref","first-page":"016114","DOI":"10.1103\/PhysRevE.72.016114","volume":"72","author":"G. Raffaelli","year":"2005","unstructured":"Raffaelli, G., Marsili, M.: Statistical mechanics model for the emergence of consensus. Physical Review E\u00a072(1), 016114 (2005)","journal-title":"Physical Review E"},{"key":"46_CR31","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics\u00a023, 493\u2013509 (1952)","journal-title":"Annals of Mathematical Statistics"},{"key":"46_CR32","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley\u2013Interscience, Chichester (2000)","edition":"2"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11821069_46.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:30:42Z","timestamp":1619508642000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11821069_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540377917","9783540377931"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/11821069_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}