Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 04. 04. 2017 19:08

Sefinek
Zelenáč
Příspěvky: 1
Pozice: student
Reputace:   
 

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

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

Offline

 

#2 04. 04. 2017 21:15

Bati
Příspěvky: 2062
Reputace:   161 
 

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

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))$.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson