A framework for algorithm stability

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

166 Downloads (Pure)

Samenvatting

We say that an algorithm is stable if small changes in the input result in small changes in the output. Algorithm stability plays an important role when analyzing and visualizing time-varying data. However, so far, there are only few theoretical results on the stability of algorithms, possibly due to a lack of theoretical analysis tools. In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees.
Originele taal-2Engels
Artikelnummer1704.08000
Aantal pagina's15
TijdschriftarXiv
StatusGepubliceerd - 26 apr. 2017

Vingerafdruk

Duik in de onderzoeksthema's van 'A framework for algorithm stability'. Samen vormen ze een unieke vingerafdruk.

Citeer dit