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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

12 Citaten (Scopus)

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

Originele taal-2	Engels
Titel	LATIN 2018: Theoretical Informatics
Subtitel	13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings
Redacteuren	M.A. Bender, M. Farach-Colton , M.A. Mosteiro
Plaats van productie	Dordrecht
Uitgeverij	Springer
Pagina's	805-819
Aantal pagina's	15
ISBN van elektronische versie	978-3-319-77404-6
ISBN van geprinte versie	978-3-319-77403-9
DOI's	https://doi.org/10.1007/978-3-319-77404-6_58
Status	Gepubliceerd - 1 jan. 2018
Evenement	13th Latin American Theoretical INformatics Symposium (LATIN 2018) - Buenos Aires, Argentinië Duur: 16 apr. 2018 → 19 apr. 2018 Congresnummer: 13 http://latin2018.dc.uba.ar/

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	10807
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	13th Latin American Theoretical INformatics Symposium (LATIN 2018)
Verkorte titel	LATIN 2018
Land/Regio	Argentinië
Stad	Buenos Aires
Periode	16/04/18 → 19/04/18
Internet adres	http://latin2018.dc.uba.ar/

Financiering

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.

Toegang tot document

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

stablemst_2018Finale auteursversie , 426 KBLicentie: Onbepaald

Andere bestanden en links

Link to publication in Scopus

Citeer dit

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 (editors), LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings (blz. 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. redacteur / M.A. Bender ; M. Farach-Colton ; M.A. Mosteiro. Dordrecht : Springer, 2018. blz. 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 (uitgave), 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, blz. 805-819, 13th Latin American Theoretical INformatics Symposium (LATIN 2018), Buenos Aires, Argentinië, 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. uitgave / M.A. Bender; M. Farach-Colton ; M.A. Mosteiro. Dordrecht: Springer, 2018. blz. 805-819 (Lecture Notes in Computer Science; Vol. 10807).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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, redacteurs, LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Dordrecht: Springer. 2018. blz. 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

Samenvatting

Publicatie series

Congres

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit