Average-case intractability vs. worst-case intractability.

Johannes Köbler Rainer Schuler

Published in: Inf. Comput. (2004)

Keyphrases

average case
worst case
np complete
worst case analysis
uniform distribution
learning curves
np hard
lower bound
upper bound
greedy algorithm
online algorithms
average case complexity
objective function
theoretical analysis