More on Average Case vs Approximation Complexity.

Michael Alekhnovich

Published in: Comput. Complex. (2011)

Keyphrases

average case
worst case
average case complexity
worst case analysis
approximation algorithms
uniform distribution
approximation error
lower bound
greedy algorithm
competitive ratio
learning curves
special case
np hard
sample complexity bounds
vc dimension
linear programming relaxation
small number
high dimensional