Beyond the Worst-Case Analysis of Algorithms
Beyond the Worst-Case Analysis of Algorithms
Tim Roughgarden Contents,Fedor V. Fomin,2 Authors,M. Zehavi
2020 · DOI: 10.1017/9781108637435
233 Citations
TLDR
This chapter sketches some techniques and tools from this rapidly developing area parameterized algorithmics, where dependence on one or more parameters of the input instance is taken into account.
Abstract
Parameterized algorithmics analyzes running time in finer detail than classical complexity theory: instead of expressing the running time of an algorithm as a function of the input size only, dependence on one or more parameters of the input instance is taken into account. In this chapter we sketch some techniques and tools from this rapidly developing area