티스토리 뷰


This means that the approximation result f(x) should be between

a) ρOPT <= f(x) <= OPT, when ρ < 1
b) OPT <= f(x) <= ρOPT, when ρ > 1

So, a) occurs when it's a maximization problem, and b) occurs when it's a minimization problem.

For example of a) when ρ=0.5, and you want to find a 0.5-approximation algorithm for a NP maximization problem of a graph G=(V,E)

when, OPT = |E|

you need to find a approximation algorithm f(x) which finds at least

0.5|E| <= f(x) <= |E|

(for 0.5-approximation in a graph, randomized algorithm almost fits to the approximation with factor 0.5)

so, if ρ becomes closer to 1, it becomes a tighter approximation algorithm.

Fin.

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함