A framework for algorithm stability and its application to kinetic Euclidean MSTs

Onderzoeksoutput: Bijdrage aan congresAbstract

44 Downloads (Pure)

Samenvatting

We say that an algorithm is stable if small changes in the input result in small changes in the output. This kind of algorithm stability is particularly relevant when analyzing and visualizing time-varying data. Stability in general plays an important role in a wide variety of areas, such as numerical analysis, machine learning, and topology, but is poorly understood in the context of (combinatorial) algorithms.

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 topological stability by applying it to kinetic Euclidean minimum spanning trees.
Originele taal-2Engels
Pagina's11:1-11:6
Aantal pagina's6
StatusGepubliceerd - 2018
Evenement34th European Workshop on Computational Geometry (EuroCG2018) - Berlin, Duitsland
Duur: 21 mrt 201823 mrt 2018
https://conference.imp.fu-berlin.de/eurocg18/home

Congres

Congres34th European Workshop on Computational Geometry (EuroCG2018)
Verkorte titelEuroCG2018
LandDuitsland
StadBerlin
Periode21/03/1823/03/18
Internet adres

    Vingerafdruk

Citeer dit

Meulemans, W., Speckmann, B., Verbeek, K. A. B., & Wulms, J. J. H. M. (2018). A framework for algorithm stability and its application to kinetic Euclidean MSTs. 11:1-11:6. Abstract van 34th European Workshop on Computational Geometry (EuroCG2018), Berlin, Duitsland.