My soon to be ex-student Ben Raichel is joining the CS department in UT Dallas.

# 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.

# Sariel

## April 1, 2015

Fracking joice! wonkette.com/581472/nebrask…

# Sariel

## April 1, 2015

gscholar-bibtex extension for emacs works well. melpa.org/?utm_source=dl…

# Sariel

## March 31, 2015

My book is now available for “free” on the internet. They did a good job scanning the book in color… bookzz.org/book/2327006/f…

# Sariel

## March 30, 2015

“Thank you for scheduling your payment.”

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

# Sariel

## March 16, 2015

More on Jirka Matousek. kam.mff.cuni.cz/Matousek-obitu…

# Sariel

## March 12, 2015

Terry Pratchett had died. bbc.com/news/entertain…

# 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.

# Sariel

## 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.

# Sariel

## March 4, 2015

2+2=5. Mostly because of rounding errors.

# Sariel

## 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.

# Sariel

## February 27, 2015

DHS funding and the singularity… sarielhp.org/blog/?p=8807

# 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…

# Sariel

## February 21, 2015

Beckett quotes over snow pictures from Boston. Surprisingly effective. mbecketta.tumblr.com

# Sariel

## February 19, 2015

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

# Sariel

## February 18, 2015

I want a recount of the temperature…

# Sariel

## February 16, 2015

I weak reject your weak reject, but I am willing to weak accept a weak accept with reservations.

# SoCG 2015 accepted papers

# Sariel

## February 13, 2015

More on the tweeters of doom… gawker.com/justine-sacco-…

# Sariel

## February 13, 2015

Blame it on a simple tweet of fate…

NYTimes: How One Stupid Tweet Blew Up Justine Sacco’s Life

nyti.ms/1zaehJD

# Sariel

## February 11, 2015

3/5.

# Just say no…

It is annoying when you ask people to referee a paper for a journal, and they do not even answer your email request. It is completely OK to refuse to referee a paper (from I am too busy, to I do not think this work is interesting, or not provide any excuse whatsoever [Sorry, I will not referee this paper.]). Just say no…

# Sariel

## February 7, 2015

The weather is sending mixed messages.

# Sariel

## February 3, 2015

Via David Eppstein. Conference deadline search confsearch.org .

# Sariel

## February 1, 2015

Typos, hypos, typhos, tyros everywhere.

# Sariel

## January 31, 2015

It seems many people around here do not know the word phlegmatic.

# Sariel

## January 27, 2015

Vanderbilt Football Players Found Guilty of Raping Unconscious Student. gawker.com/vanderbilt-foo…

# Sariel

## January 26, 2015

404: Plane not found. nbcnews.com/storyline/isis…