ls11-www.cs.tu-dortmund.de/_media/buchin/teaching/akda_ws21/geometric-set-cover.pdf
6. returnR′
1 red = {1, 2, 3, 4, 5, 7, 8} 1 green = {1, 2, 7, 8} 1 orange = {1, 2, 3, 4, 7, 8}
6
8
2 3 1 4
5 7
W (r)
Let ε = 2/3 and |R′| = 2
2 2 2
5. sample newR′
2 2 4
2 2 2sampleR′, e.g.,R′ = {red, [...] sample newR′ 6. returnR′
1 red = {1, 2, 3, 4, 5, 7, 8} 1 green = {1, 2, 7, 8} 1 orange = {1, 2, 3, 4, 7, 8}
6
8
2 3 1 4
5 7
W (r)
Let ε = 2/3 and |R′| = 2
2 2 2
2 2 4
2 2 2sampleR′, e.g.,R′ = {red, pink}
R′ [...] red = {1, 2, 3, 4, 5, 7, 8} 1 green = {1, 2, 7, 8} 1 orange = {1, 2, 3, 4, 7, 8}
6
8
2 3 1 4
5 7
W (r)
2 2 2
2 2 4
2 2 2
intuition:
1. With probability 1/2: R′ is ε-net
The algorithm
1 blue = {2, 3, 5, 6} …
