[I did rephrase the report a bit, and I am happy I helped making the conference more selective. Mark me as being amused.]

]]>Given a set system \((S,F)\) with \(n = |S|\) elements, and \(m=|F|\) sets, consider the algorithm that starts with all the elements having weight \(1\). At every iteration, the algorithm picks the heaviest set (taking into account the weight of all the elements – not only the uncovered ones as in the standard greedy algorithm). Next, the algorithm doubles the weight of all the uncovered elements. Question: What is the approximation quality of this algorithm?

The answer:

]]>The trick is to divide the weight of the covered elements in every iterations instead of multiplying the weight of the uncovered elements. Clearly, up to a scaling by a factor of two, the two operations are equivalent, and in particular this preserve the relative order of the sets. Observe, that an uncovered element has weight \(1\) till it is covered for the first time. In particular, let \(W_0 = |n|\), and let \(W_i\) be the total weight of \(S\) in the beginning of the \(i\)th iteration. Let \(x_i\) be the weight of the set picked in the \(i\)th iteration, and observe that \(x_i \geq W_i/k\), where \(k\) is the number of sets in the optimal solution. Furthermore, \(W_{i+1} \leq W_i – x_{i}/2 \leq (1-1/2k) W_i\), as the weight of the elements of the set covered in the \(i\)th iteration get their weight halved. We conclude that \(W_{O(k \log n)} <1\), which implies that all the elements are covered in the end of the \(O( k \log n)\) iteration. Thus, this is \(O( \log n)\) approximation.

“No, no, thank you for taking my money!” ]]>

I feel inadequate to summarize Jirka’s research. From his work on partitions trees, discrepancy, embeddings, topology, linear-programming, derandomization, cuttings, approximation algorithms, discrete geometry and much much more.

Quoting from the email I got with this sad news: “He will further live with us through our memories and in his excellent books and papers.”

May he rest in peace.

]]>