Frequency of correctness versus average polynomial time

DOI10.1016/J.IPL.2009.05.001MaRDI QIDQ989533zbMATH OpenOpenAlexFDO

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

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)

Cites work

• scientific article; zbMATH DE number 3148878 (Why is no real title available?)
• scientific article; zbMATH DE number 1072538 (Why is no real title available?)
• Approximability of Dodgson's rule
• Average Case Complete Problems
• Complete sets and closeness to complexity classes
• Exact analysis of Dodgson elections
• Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners
• Notes on Levin's theory of average-case complexity
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989533)