Frequency of correctness versus average polynomial time

DOI10.1016/J.IPL.2009.05.001zbMATH Open1200.68124OpenAlexW2086276791MaRDI QIDQ989533FDOQ989533

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

• Title not available (Why is that?)
• Voting schemes for which it can be difficult to tell who won the election
• Exact analysis of Dodgson elections
• Average Case Complete Problems
• Complete sets and closeness to complexity classes
• Title not available (Why is that?)
• Notes on Levin's theory of average-case complexity
• Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners
• Approximability of Dodgson's rule

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)