Frequency of correctness versus average polynomial time

DOI10.1016/J.IPL.2009.05.001zbMath1200.68124OpenAlexW2086276791MaRDI QIDQ989533

Holger Spakowski, Gábor Erdélyi, Jörg Rothe, Hemaspaandra, Lane A.

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.05.001

zbMATH Keywords

computational complexityheuristicsanalysis of algorithmsaverage-case complexityAvgPfrequently self-knowingly correct algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (3)

Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Control complexity in Bucklin and fallback voting: an experimental analysis ⋮ Computational Aspects of Approval Voting

Cites Work

• Unnamed Item
• Unnamed Item
• Approximability of Dodgson's rule
• Voting schemes for which it can be difficult to tell who won the election
• Notes on Levin’s Theory of Average-Case Complexity
• Average Case Complete Problems
• Exact analysis of Dodgson elections
• Complete sets and closeness to complexity classes
• Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners

This page was built for publication: Frequency of correctness versus average polynomial time