View publication
| Title | From Adaptive Analysis to Instance Optimality |
| Authors | Jérémy Barbay |
| Publication date | 2021 |
| Abstract |
Parameterized analysis techniques are not limited to NP hard problems, they also yield results on more tractable problems. This chapter introduces the concepts of /adaptive analysis/ and /instance optimality/: the adaptive analysis reduces the scope over which the worst case is taken to smaller classes, eventually down to various notions of instance optimality. Developped since the 70's, such analysis techniques have become even more relevant nowadays as the size of data explodes, and with it the gap between the worst case performance and the typical one. We present a sequence of results on an exemplary problem, the computation of Maxima Sets; a (non exhaustive but representative) list of other techniques and results; and we discuss some related open problems and perspectives. |
| Downloaded | 7 times |
| Pages | 52-71 |
|
|
| Reference URL |
|