On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
Gábor ErdélyiLane A. HemaspaandraJörg RotheHolger SpakowskiPublished in: CoRR (2007)
Keyphrases
- average case
- worst case
- worst case analysis
- competitive ratio
- learning curves
- approximation algorithms
- greedy algorithm
- np hard
- uniform distribution
- sample size
- np hardness
- dynamic programming
- lower bound
- upper bound
- special case
- computational complexity
- average case complexity
- machine learning
- online algorithms
- vc dimension
- data compression
- theoretical analysis