More on Average Case vs Approximation Complexity.

Michael Alekhnovich

Published in: FOCS (2003)

Keyphrases

average case
worst case
average case complexity
worst case analysis
approximation algorithms
approximation error
uniform distribution
learning curves
upper bound
greedy algorithm
lower bound
competitive ratio
data sets
vc dimension
np hardness
sample size
computational complexity
machine learning