SoCG 2015 Proceedings…

Are now available online for free, well before the conference.

The formatting is much nicer than the ACM formatting, and the usual formatting used in theory conferences proceedings. Yet another reason to move away from ACM/IEEE.


April 18, 2015

T-Shirt weather, sunny, green. Unwhining about spring time.

The latest referee report I got…

The results in this paper are known and obvious, on a new strange problem that the authors define but nobody cares about. Thus, one must conclude that the authors wrote the paper just because they like the clicking sounds made by the keyboard as they typed their paper. Also, all the words used in the paper can be found in a dictionary, so there is nothing new in this paper.

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

Set cover via increasing weights

Somebody asked this on Theory stack exchange and then deleted the question after I answered it (I assume it is a standard homework problem). Since I liked the problem, here is the question and answer.

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.


April 9, 2015

Spend hours making your spam filter better, and then when you want spam to test it, no spam arrives.


March 30, 2015

“Thank you for scheduling your payment.”
“No, no, thank you for taking my money!”

Sad news

Jirka Matousek had died yesterday (Monday, March 9, 2015) after a long illness at age 52. Today would have been his birthday. Not only was Jirka an amazing researcher, but he had written several important books, from his wonderful book on discrepancy, to his equally great book on discrete geometry, to his book on the Borsuk-Ulam theorem, and his (coauthored) introductory book on discrete math. See his webpage for more information about his books and papers.

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.


March 9, 2015

There should be an expression describing the undertaking of bounding a constant till it can no longer breath, and it is ready to serve.


March 3, 2015

Weather app I use is going through hard times. Says Saturday weather is going to be dreary. Too depressed to to discuss Sunday weather.

The singularity is coming…

So the house extended DHS funding by one week. Previously, the funding was for a year, I assume. So, the funding period just shrank by a factor of (roughly) 50. Next week they are going to extend the funding by 3.3 hours, then followed by funding the DHS for 4 minutes, then the DHS would be funded by 5 seconds, and after that, for all practical purposes, we are going to hit the singularity on this piece of legislation.

Get all the homeland security you can get now, before it hits the singularity…

I just have to wonder where all the grownups are.

The article


February 19, 2015

YOFDO = You only freeze to death once (it is -18C here now).