A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs
A Framework for Algorithm Stability and Its Application to Kinetic Euclidean MSTs
复制标题
算法稳定性框架及其在动力学欧氏MST中的应用
DOI：
10.1007/978-3-319-77404-6_58
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
J. Wulms
中科院分区：
文献类型：
--
作者：
Wouter Meulemans;B. Speckmann;Kevin Verbeek;J. Wulms
我们说一个算法是稳定的，如果输入的微小变化导致输出的微小变化。当分析和可视化时变数据时，这种算法的稳定性特别重要。稳定性一般在各种各样的领域，如数值分析，机器学习和拓扑学中起着重要的作用，但在（组合）algorithms.In本文中，我们提出了一个框架，分析算法的稳定性的背景下了解甚少。我们特别关注算法的稳定性和它计算的解决方案的质量之间的权衡。我们的框架允许三种类型的稳定性分析与日益增加的复杂程度：事件稳定性，拓扑稳定性和Lipschitz稳定性。我们证明了使用我们的稳定性框架，将其应用到动态欧氏最小生成树。
We say that an algorithm isstableif 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.
影响因子：
2.1
作者：
通讯作者：
--