{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T19:27:10Z","timestamp":1710271630598},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,12,28]],"date-time":"2007-12-28T00:00:00Z","timestamp":1198800000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2009,8]]},"DOI":"10.1007\/s10732-007-9068-5","type":"journal-article","created":{"date-parts":[[2007,12,27]],"date-time":"2007-12-27T12:46:51Z","timestamp":1198759611000},"page":"403-423","source":"Crossref","is-referenced-by-count":17,"title":["Guarantees for the success frequency of an algorithm for finding Dodgson-election winners"],"prefix":"10.1007","volume":"15","author":[{"given":"Christopher M.","family":"Homan","sequence":"first","affiliation":[]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,12,28]]},"reference":[{"issue":"1","key":"9068_CR1","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 150(1), 1\u201355 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9068_CR2","doi-asserted-by":"crossref","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, New York (2000)","edition":"2"},{"key":"9068_CR3","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":"9068_CR4","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.\u00a0206\u2013207. ACM, New York (2001)"},{"issue":"4","key":"9068_CR5","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1137\/S0097539705446974","volume":"36","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for NP problems. SIAM J. Comput. 36(4), 1119\u20131159 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9068_CR6","doi-asserted-by":"crossref","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. Soc. Choice Welf. 6(2), 157\u2013165 (1989)","journal-title":"Soc. Choice Welf."},{"issue":"6","key":"9068_CR7","doi-asserted-by":"crossref","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 J. Comput. 17(6), 1232\u20131252 (1988)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9068_CR8","doi-asserted-by":"crossref","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. Ann. Math. Stat. 23(4), 493\u2013509 (1952)","journal-title":"Ann. Math. Stat."},{"issue":"3","key":"9068_CR9","first-page":"418","volume":"23","author":"L. Chang","year":"1976","unstructured":"Chang, L., Korsh, J.: Canonical coin changing and greedy solutions. J.\u00a0ACM 23(3), 418\u2013422 (1976)","journal-title":"J.\u00a0ACM"},{"key":"9068_CR10","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press\/McGraw\u2013Hill, Cambridge\/New York (2001)","edition":"2"},{"key":"9068_CR11","first-page":"627","volume-title":"Proceedings of the 21st National Conference on Artificial Intelligence","author":"V. Conitzer","year":"2006","unstructured":"Conitzer, V., Sandholm, T.: Nonexistence of voting rules that are usually hard to manipulate. In: Proceedings of the 21st National Conference on Artificial Intelligence, pp.\u00a0627\u2013634. AAAI Press, Menlo Park (2006)"},{"key":"9068_CR12","unstructured":"de Borda, J.: M\u00e9moire sur les \u00e9lections au scrutin. Hist. Acad. Roy. Sci. Ann. 1781 (1784)"},{"key":"9068_CR13","unstructured":"de Caritat, M.J.A.N.: Marquis de Condorcet. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix (1785). Facsimile reprint of original published in Paris, 1972, by the Imprimerie Royale"},{"key":"9068_CR14","unstructured":"Dodgson, C.: A method of taking votes on more than two issues. Pamphlet printed by the Clarendon Press, Oxford, and headed \u201cnot yet published\u201d (see the discussions in McLean and Urken (1995) and Black (1958), both of which reprint this paper) (1876)"},{"key":"9068_CR15","first-page":"147","volume-title":"Proceedings of the 18th Annual IEEE Conference on Computational Complexity","author":"R. Downey","year":"2003","unstructured":"Downey, R.: Parameterized complexity for the skeptic. In: Proceedings of the 18th Annual IEEE Conference on Computational Complexity, pp.\u00a0147\u2013168. IEEE Computer Society, Los Alamitos (2003)"},{"key":"9068_CR16","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, Berlin (1999)"},{"key":"9068_CR17","unstructured":"Erd\u00e9lyi, G., Hemaspaandra, L., Rothe, J., Spakowski, H.: On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time. Technical Report TR-914, Department of Computer Science, University of Rochester, Rochester, NY (March 2007)"},{"key":"9068_CR18","first-page":"641","volume-title":"Proceedings of the 21st National Conference on Artificial Intelligence","author":"P. Faliszewski","year":"2006","unstructured":"Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: The complexity of bribery in elections. In: Proceedings of the 21st National Conference on Artificial Intelligence, pp.\u00a0641\u2013646. AAAI Press, Menlo Park (2006a)"},{"key":"9068_CR19","unstructured":"Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: How hard is bribery in elections? Technical Report TR-895, Department of Computer Science, University of Rochester, Rochester, NY, April 2006. Revised (September 2006b)"},{"key":"9068_CR20","unstructured":"Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Llull and Copeland voting broadly resist bribery and control. In: Proceedings of the 22nd National Conference on Artificial Intelligence, pp.\u00a0724\u2013730. AAAI Press, Menlo Park (2007)"},{"key":"9068_CR21","first-page":"359","volume-title":"Proceedings of the 16th ACM Symposium on Theory of Computing","author":"A. Goldberg","year":"1984","unstructured":"Goldberg, A., 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.\u00a0359\u2013368. ACM, New York (1984)"},{"issue":"97","key":"9068_CR22","first-page":"3","volume":"41","author":"G. H\u00e4gele","year":"2001","unstructured":"H\u00e4gele, G., Pukelsheim, F.: The electoral writings of Ramon Llull. Stud. Lulliana 41(97), 3\u201338 (2001)","journal-title":"Stud. Lulliana"},{"issue":"3","key":"9068_CR23","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"Hemachandra, L.: The strong exponential hierarchy collapses. J.\u00a0Comput. Syst. Sci. 39(3), 299\u2013322 (1989)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9068_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/3-540-44612-5_5","volume-title":"Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science","author":"E. Hemaspaandra","year":"2000","unstructured":"Hemaspaandra, E., Hemaspaandra, L.: Computational politics: electoral systems. In: Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 1893, pp.\u00a064\u201383. Springer, Berlin (2000)"},{"issue":"6","key":"9068_CR25","first-page":"806","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. J.\u00a0ACM 44(6), 806\u2013825 (1997)","journal-title":"J.\u00a0ACM"},{"issue":"3","key":"9068_CR26","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. Theor. Comput. Sci. 349(3), 382\u2013391 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9068_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1007\/11821069_46","volume-title":"Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science","author":"C. Homan","year":"2006","unstructured":"Homan, C., Hemaspaandra, L.: Guarantees for the success frequency of an algorithm for finding Dodgson-election winners. In: Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 4162, pp.\u00a0528\u2013539. Springer, Berlin (2006)"},{"key":"9068_CR28","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1109\/SCT.1995.514853","volume-title":"Proceedings of the 10th Structure in Complexity Theory Conference","author":"R. Impagliazzo","year":"1995","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of the 10th Structure in Complexity Theory Conference, pp.\u00a0134\u2013147. IEEE Computer Society, Los Alamitos (1995)"},{"issue":"6","key":"9068_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 J.\u00a0Comput. 17(6), 1263\u20131282 (1988). Erratum appears in the same journal 20(2), 404","journal-title":"SIAM J.\u00a0Comput."},{"key":"9068_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1007\/3-540-45749-6_51","volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms","author":"A. Kaporis","year":"2002","unstructured":"Kaporis, A., Kirousis, L., Lalas, E.: The probabilistic analysis of a greedy satisfiability algorithm. In: Proceedings of the 10th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 2461, pp.\u00a0574\u2013585. Springer, Berlin (2002)"},{"issue":"4","key":"9068_CR31","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H. Lenstra Jr.","year":"1983","unstructured":"Lenstra, H. Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9068_CR32","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"Levin, L.: Average case complete problems. SIAM J.\u00a0Comput. 15(1), 285\u2013286 (1986)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9068_CR33","unstructured":"McCabe-Dansted, J., Pritchard, G., Slinko, A.: Approximability of Dodgson\u2019s rule. In: Endriss,\u00a0U., Lang,\u00a0J.\u00a0(eds.) Proceedings of the 1st International Workshop on Computational Social Choice, pp.\u00a0331\u2013344. Universiteit van Amsterdam (2006). Available online at staff.science.uva.nl\/~ulle\/COMSOC-2006\/proceedings.html"},{"key":"9068_CR34","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":"9068_CR35","first-page":"197","volume":"19","author":"E. Nanson","year":"1882","unstructured":"Nanson, E.: Methods of election. Trans. Proc. Roy. Soc. Vic. 19, 197\u2013240 (1882)","journal-title":"Trans. Proc. Roy. Soc. Vic."},{"key":"9068_CR36","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Habilitation thesis, University of T\u00fcbingen (2002)"},{"key":"9068_CR37","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1613\/jair.2148","volume":"28","author":"A. Procaccia","year":"2007","unstructured":"Procaccia, A., Rosenschein, J.: Junta distributions and the average-case complexity of manipulating elections. J.\u00a0Artif. Intell. Res. 28, 157\u2013181 (2007)","journal-title":"J.\u00a0Artif. Intell. Res."},{"key":"9068_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1007\/3-540-12689-9_118","volume-title":"Proceedings of the 4th Conference on Fundamentals 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: Proceedings of the 4th Conference on Fundamentals of Computation Theory. Lecture Notes in Computer Science, vol. 158, pp.\u00a0360\u2013367. Springer, Berlin (1983)"},{"key":"9068_CR39","series-title":"Lecture Notes in Computer Science","first-page":"269","volume-title":"Proceedings of the 6th GI Conference on Theoretical Computer Science","author":"C. Papadimitriou","year":"1983","unstructured":"Papadimitriou, C., Zachos, S.: Two remarks on the power of counting. In: Proceedings of the 6th GI Conference on Theoretical Computer Science. Lecture Notes in Computer Science, vol. 145, pp.\u00a0269\u2013276. Springer, Berlin (1983)"},{"issue":"1","key":"9068_CR40","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. Phys. Rev. E 72(1), 016114 (2005)","journal-title":"Phys. Rev. E"},{"issue":"4","key":"9068_CR41","doi-asserted-by":"crossref","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 Comput. Syst. 36(4), 375\u2013386 (2003)","journal-title":"Theory Comput. Syst."},{"key":"9068_CR42","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Computation","year":"1983","unstructured":"Sankoff, D., Kruskal, J. (eds.): Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Computation. Addison\u2013Wesley, Reading (1983)"},{"issue":"2","key":"9068_CR43","doi-asserted-by":"crossref","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. J.\u00a0Algorithms 25(2), 237\u2013254 (1997)","journal-title":"J.\u00a0Algorithms"},{"issue":"3","key":"9068_CR44","first-page":"385","volume":"51","author":"D. Spielman","year":"2004","unstructured":"Spielman, D., Teng, S.: Smoothed analysis: Why the simplex algorithm usually takes polynomial time. J.\u00a0ACM 51(3), 385\u2013463 (2004)","journal-title":"J.\u00a0ACM"},{"key":"9068_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/3-540-44450-5_28","volume-title":"Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"H. Spakowski","year":"2000","unstructured":"Spakowski, H., Vogel, J.: \u0398 2 p -completeness: A classical approach for new results. In: Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1974, pp.\u00a0348\u2013360. Springer, Berlin (2000)"},{"key":"9068_CR46","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.\u00a0157\u2013168. SADIO (2001)"},{"issue":"3","key":"9068_CR47","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/BF00433944","volume":"4","author":"T. Tideman","year":"1987","unstructured":"Tideman, T.: Independence of clones as a criterion for voting rules. Soc. Choice Welf. 4(3), 185\u2013206 (1987)","journal-title":"Soc. Choice Welf."},{"key":"9068_CR48","unstructured":"Trevisan, L.: Lecture notes on computational complexity. www.cs.berkeley.edu\/~luca\/notes\/complexitynotes02.pdf (Lecture 12) (2002)"},{"issue":"1\u20132","key":"9068_CR49","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 51(1\u20132), 53\u201380 (1987)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9068_CR50","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K. Wagner","year":"1990","unstructured":"Wagner, K.: Bounded query classes. SIAM J.\u00a0Comput. 19(5), 833\u2013846 (1990)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9068_CR51","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/978-1-4612-1872-2_12","volume-title":"Complexity Theory Retrospective II","author":"J. Wang","year":"1997","unstructured":"Wang, J.: Average-case computational complexity theory. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II, pp.\u00a0295\u2013328. Springer, Berlin (1997a)"},{"key":"9068_CR52","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-1-4613-3394-4_15","volume-title":"Advances in Languages, Algorithms, and Complexity","author":"J. Wang","year":"1997","unstructured":"Wang, J.: Average-case intractable NP problems. In: Du, D., Ko, K. (eds.) Advances in Languages, Algorithms, and Complexity, pp.\u00a0313\u2013378. Kluwer Academic, Dordrecht (1997b)"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-007-9068-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10732-007-9068-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-007-9068-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T18:54:29Z","timestamp":1559242469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10732-007-9068-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,28]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["9068"],"URL":"https:\/\/doi.org\/10.1007\/s10732-007-9068-5","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,28]]}}}