19.12.2017  Technical Contribution  Ausgabe 1/2018 Open Access
CoresetsMethods and History: A Theoreticians Design Pattern for Approximation and Streaming Algorithms
 Zeitschrift:
 KI  Künstliche Intelligenz > Ausgabe 1/2018
1 Introduction

Geometric decompositions.

Gradient descent.

Random sampling.

Sketching and projections.
2 Preliminaries
3 Construction Techniques
3.1 Geometric Decompositions
3.2 Gradient Descent
3.3 Random Sampling
3.4 Sketches and Projections
4 Streaming
Algorithm  Offline memory  Streaming memory 

Low dimensions  
[58] 
\(O(k\varepsilon ^{d}\log n)\)

\(O(k\varepsilon ^{(d+1)} \log ^{2d+2} n)\)

[57] 
\(O(k^3 \varepsilon ^{(d+1)})\)

\(O(k^3 \varepsilon ^{(d+1)} \log ^{d+2} n)\)

[52] 
\(O(k\varepsilon ^{d}\log n )\)

\(O(k\varepsilon ^{(d+2)}\log ^4 n)\)

[51] 
\(O(k\varepsilon ^{(d+2)}\log n)\)

\(O(k\varepsilon ^{(d+2)}\log n)\)

High dimensions  
[27] 
\(O(d^2k^2\varepsilon ^{2}\log ^5 n)\)

\(O(d^2k^2 \varepsilon ^{2}\log ^9 n)\)

[46] 
\(O(k^2\varepsilon ^{5})\)

\(O(k^2 \varepsilon ^{5}\log ^{7} n)\)

[71] 
\(O(d^2k^3\varepsilon ^{2})\)

\(O(d^2k^3\varepsilon ^{2}\log ^4 n)\)

[45] 
\(O(dk\varepsilon ^{4})\)

\(O(dk\varepsilon ^{4}\log ^{6} n)\)
