We present a technical survey on the state of the art approaches in data reduction and the coreset framework. These include geometric decompositions, gradient methods, random sampling, sketching and random projections. We further outline their importance for the design of streaming algorithms and give a brief overview on lower bounding techniques.
Dettaglio pubblicazione
2018, KI. KUNSTLICHE INTELLIGENZ, Pages 37-53 (volume: 32)
Coresets-Methods and History: A Theoreticians Design Pattern for Approximation and Streaming Algorithms (01a Articolo in rivista)
Munteanu Alexander, Schwiegelshohn Chris
Gruppo di ricerca: Algorithms and Data Science
keywords