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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
124 Downloads (Pure)

Abstract

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 our stability framework by applying it to kinetic Euclidean minimum spanning trees.

Original languageEnglish
Title of host publicationLATIN 2018: Theoretical Informatics
Subtitle of host publication13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings
EditorsM.A. Bender, M. Farach-Colton , M.A. Mosteiro
Place of PublicationDordrecht
PublisherSpringer
Pages805-819
Number of pages15
ISBN (Electronic)978-3-319-77404-6
ISBN (Print)978-3-319-77403-9
DOIs
Publication statusPublished - 1 Jan 2018
Event13th Latin American Theoretical INformatics Symposium (LATIN 2018) - Buenos Aires, Argentina
Duration: 16 Apr 201819 Apr 2018
Conference number: 13
http://latin2018.dc.uba.ar/

Publication series

NameLecture Notes in Computer Science
Volume10807
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th Latin American Theoretical INformatics Symposium (LATIN 2018)
Abbreviated titleLATIN 2018
Country/TerritoryArgentina
CityBuenos Aires
Period16/04/1819/04/18
Internet address

Fingerprint

Dive into the research topics of 'A framework for algorithm stability and its application to kinetic euclidean MSTs'. Together they form a unique fingerprint.

Cite this