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

Wouter Meulemans; Bettina Speckmann; Kevin Verbeek; Jules Wulms

doi:10.1007/978-3-319-77404-6_58

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

Wouter Meulemans, Bettina Speckmann, Kevin Verbeek, Jules Wulms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

12 Citations (Scopus)

357 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 language	English
Title of host publication	LATIN 2018: Theoretical Informatics
Subtitle of host publication	13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings
Editors	M.A. Bender, M. Farach-Colton , M.A. Mosteiro
Place of Publication	Dordrecht
Publisher	Springer
Pages	805-819
Number of pages	15
ISBN (Electronic)	978-3-319-77404-6
ISBN (Print)	978-3-319-77403-9
DOIs	https://doi.org/10.1007/978-3-319-77404-6_58
Publication status	Published - 1 Jan 2018
Event	13th Latin American Theoretical INformatics Symposium (LATIN 2018) - Buenos Aires, Argentina Duration: 16 Apr 2018 → 19 Apr 2018 Conference number: 13 http://latin2018.dc.uba.ar/

Publication series

Name	Lecture Notes in Computer Science
Volume	10807
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th Latin American Theoretical INformatics Symposium (LATIN 2018)
Abbreviated title	LATIN 2018
Country/Territory	Argentina
City	Buenos Aires
Period	16/04/18 → 19/04/18
Internet address	http://latin2018.dc.uba.ar/

Funding

W. Meulemans and J. Wulms are (partially) supported by the Netherlands eScience Center (NLeSC) under grant number 027.015.G02. B. Speckmann and K. Verbeek are supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208 and no. 639.021.541, respectively.

Access to Document

10.1007/978-3-319-77404-6_58

stablemst_2018Final author version , 426 KBLicence: Unspecified

Cite this

Meulemans, W., Speckmann, B., Verbeek, K., & Wulms, J. (2018). A framework for algorithm stability and its application to kinetic euclidean MSTs. In M. A. Bender, M. Farach-Colton , & M. A. Mosteiro (Eds.), LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings (pp. 805-819). (Lecture Notes in Computer Science; Vol. 10807). Springer. https://doi.org/10.1007/978-3-319-77404-6_58

Meulemans, Wouter ; Speckmann, Bettina ; Verbeek, Kevin et al. / A framework for algorithm stability and its application to kinetic euclidean MSTs. LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. editor / M.A. Bender ; M. Farach-Colton ; M.A. Mosteiro. Dordrecht : Springer, 2018. pp. 805-819 (Lecture Notes in Computer Science).

@inproceedings{bde45eae314a42b48dca9a0a420f38e1,

title = "A framework for algorithm stability and its application to kinetic euclidean MSTs",

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.",

author = "Wouter Meulemans and Bettina Speckmann and Kevin Verbeek and Jules Wulms",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-77404-6_58",

language = "English",

isbn = "978-3-319-77403-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "805--819",

editor = "M.A. Bender and {Farach-Colton }, M. and M.A. Mosteiro",

booktitle = "LATIN 2018: Theoretical Informatics",

address = "Germany",

note = "13th Latin American Theoretical INformatics Symposium (LATIN 2018), LATIN 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

url = "http://latin2018.dc.uba.ar/",

}

Meulemans, W , Speckmann, B , Verbeek, K & Wulms, J 2018, A framework for algorithm stability and its application to kinetic euclidean MSTs. in MA Bender, M Farach-Colton & MA Mosteiro (eds), LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10807, Springer, Dordrecht, pp. 805-819, 13th Latin American Theoretical INformatics Symposium (LATIN 2018), Buenos Aires, Argentina, 16/04/18. https://doi.org/10.1007/978-3-319-77404-6_58

A framework for algorithm stability and its application to kinetic euclidean MSTs. / Meulemans, Wouter ; Speckmann, Bettina ; Verbeek, Kevin et al.
LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. ed. / M.A. Bender; M. Farach-Colton ; M.A. Mosteiro. Dordrecht: Springer, 2018. p. 805-819 (Lecture Notes in Computer Science; Vol. 10807).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Meulemans, Wouter

AU - Speckmann, Bettina

AU - Verbeek, Kevin

AU - Wulms, Jules

N1 - Conference code: 13

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85045401436&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-77404-6_58

DO - 10.1007/978-3-319-77404-6_58

M3 - Conference contribution

AN - SCOPUS:85045401436

SN - 978-3-319-77403-9

T3 - Lecture Notes in Computer Science

SP - 805

EP - 819

BT - LATIN 2018: Theoretical Informatics

A2 - Bender, M.A.

A2 - Farach-Colton , M.

A2 - Mosteiro, M.A.

PB - Springer

CY - Dordrecht

T2 - 13th Latin American Theoretical INformatics Symposium (LATIN 2018)

Y2 - 16 April 2018 through 19 April 2018

ER -

Meulemans W , Speckmann B , Verbeek K , Wulms J. A framework for algorithm stability and its application to kinetic euclidean MSTs. In Bender MA, Farach-Colton M, Mosteiro MA, editors, LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Dordrecht: Springer. 2018. p. 805-819. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-77404-6_58

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

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this