Pergunta

I'm reading the following article that presents a $log(k)$ algorithm for your secretary problem.

I'm in the analysis section at the left part of page 5 there is the following claim:

$B^*$ is a set with elements $x_1,...,x_k$ with respective values $v_1,...,v_k$ where $v_1\geq...\geq v_k$. Denote $n_i(B^*)$ as the number of elements in $B^*$ with value at least $v_i$. Then the sum of the $q$ largest elements is $[\sum_{i=1}^{q-1}(v_{i+1}-v_{i})n_{i}(B^{*})]+v_{q}n_{q}(B^{*})$

I fail to see how the sum presented is the sum of the largest $q$ elements. From what I understand $n_{i}(B^{*})=i$ since the elements with value at least $v_{i} $ are $v_{1},...,v_{i}$.

If I open the sum than all the inner element ($v_{2},...,v_{q-1}$) has a coefficient of $1$, but the coefficient of $v_{1}$ is $-1$ and the coefficient of $v_{q}$ is $2q$.

Can someone help me understand this equality?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top