nRecent trend: study of
average/empirical hardness as opposed to the worst-case complexity
(NP-Hardness) [Cheeseman
et al.; Selman et
al.]
nOur proposal: predict
the running time of an algorithm on a particular instance
based on features of that instance
nToday:
na methodology for doing this
nits application to the combinatorial auction winner
determination problem (WDP)
n