| Stability, Adaptivity, and Dynamic Algorithms (2008) | |||||||||||||||
Abstract | |||||||||||||||
| A dynamic algorithm maintains the relationship between its input and output as the input changes online. In previous work, researchers developed dynamic algorithms on a per problem basis by using techniques that are well-suited for that particular problem. Although many of the resulting algorithms are similar to their static counterparts, the relationship between them is not well understood. Some attempts to this end has been made by devising techniques for automatically making static algorithms dynamic but they remained limited in their applicability. As my thesis work, I propose to develop an analytical framework for measuring the potential of a static algorithm as a dynamic algorithm and to develop programming language facilities to realize this potential. The analytical framework would enable one to design an algorithm that would be efficient when made dynamic. The language would make the implementation of a dynamic algorithm nearly as easy as its static counterpart. 1 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||