Matematické Fórum

Sefinek · 04. 04. 2017 19:08

Zdravím, řeším důkaz, že problém minimum set cover je v APX(1 + ln n). Našel jsem tento důkaz docela dobře vysvětlený, ale v závěru je jedna věc, která se tam uvádí jako jasná, ale mě vůbec jasná není. Jedná se o to, že suma $1 + \frac{1}{2} + \ldots + \frac{1}{n}$ se nachází mezi $\ln n$ a $1 + \ln n$ . K tomu je tam doslova napsáno "This is easy to see by looking at the graph of y = 1/x and its integral from 1 to d which is $\ln d$ ." (kdyžtak důkaz je zde https://people.cs.umass.edu/~barring/cs … ure/21.pdf na prvních asi 6 stránkách)

Ještě rozumím tomu, odkud se vzalo to $\ln n$ , protože integrál funkce 1/x je opravdu $\ln n$ , ale nechápu, odkud se vzalo to omezení $1 + \ln n$ . Dokázal by mi to prosím někdo vysvětlit?

Díky

Bati · 04. 04. 2017 21:15

Ahoj,
označím $s(x)=\sum_{k=1}^{\infty}\frac1{k+1}\chi_{[k,k+1)}(x)$ , $x>0$ , příslušnou schodovitou funkci. Pak si můžeš snadno ověřit, že platí
$\frac1{x+1}\leq s(x)\leq\frac1x$ , $x>0$ ,
a integrací té nerovnosti přes $[1,n]$ bys měl najít odhady co potřebuješ. Ten spodní asi vyjde trochu ostřeji než $\ln n$ , asi $\ln(\tfrac{e}2(n+1))$ .

Matematické Fórum

#1 04. 04. 2017 19:08

Důkaz, že minimum set cover je v APX(1 + ln n)

#2 04. 04. 2017 21:15

Re: Důkaz, že minimum set cover je v APX(1 + ln n)

Zápatí