Survey on Hardness of Approximation

In 2004 I wrote a survey on hardness of approximation as a book chapter for a book on approximation algorithm. I have just prepared a revised version for a new edition of the book.

While it would have been preferable to rethink the organization and start from scratch, because of time constraints I was only able to add sections on integrality gaps and on unique games, and to add references to more recent work (e.g. the combinatorial proof of the PCP theorem, the new 2-query PCPs, the tight results on minimizing congestion in directed networks, and so on).

If your (or your friend’s) important results are not cited, do let me know. The deadline to submit the chapter has long passed, but the threats from the editor haven’t yet escalated to the point where I feel that I have to submit it or else.


The Mystery Lamp

I have to buy a lamp for my office desk, and I was planning to either buy the Tizio lamp, which I have at home and that I think is the most beautiful desk lamp in production, or the Tolomeo, which works better in terms of actually illuminating, and is almost as good-looking.

Searching online, I found out that, apparently, since 2006 Artemide has been making an LED version of the Tolomeo

which looks amazing. I have, however, never seen it in a store, I haven’t been able to find any review on the web other than the marketing information from Artemide, and, while it can be ordered online, it seems that no store in San Francisco has it in store to check it out.

Usually, the light of LEDs is cold and unpleasant, so I wouldn’t buy it sight unseen. (Plus, it’s supposed to be quite small, so I am afraid it could be too small for a large desk.) So I turn to the powers of the internet: have you, or maybe your roommate’s sister in law’s cousin, seen it in real life?

If not, has any of you used an LED lamp as a desk light? How did it work out for you?

Lies, Damn Lies, and National Review (Part III)

Deroy Murdock writes about the snow that has been falling in North America (not Vancouver, though!) and Europe in the past three months:

Forty-nine of these 50 United States simultaneously laughed at “global warming.” Absent Hawaii, every state in the Union had measurable snow on Saturday, February 13. An average eight inches covered 68.1 percent of the continental U.S., well above January’s more typical 51.2 percent. Mobile, Ala., saw its first snow in twelve years. Shreveport, La., got 5.4 inches. Dallas residents coped with 12.5 inches of snow — a one-day record.

Florida’s unusually cold coastal waters (in the 40s, in some places) have killed a record 280 manatees through February 12. As CNN reports, manatees like it above 68 degrees. Some now warm themselves in the 78-degree discharge of a Tampa Electric Company power plant.
February 12’s storm followed a Nor’easter that shuttered Washington, D.C.’s federal offices for four days. Through February 14, this winter’s 55.9 inches of snow smothered Washington’s previous record, 54.4 inches, from winter 1898–1899.

How about last month?

“In Europe, snowstorms and sub-zero temperatures severely disrupted air, rail, and road transport,” the U.S. National Ice Center’s Sean R. Helfrich concluded January 12. “The snow events impacted hundreds of millions of people world-wide, with a number of weather-related deaths reported.”

Meanwhile, December’s snow cover was North America’s greatest, and the Northern Hemisphere’s second greatest, in the 44 years measured.

Warmists correctly retort that three frigid months establish no pattern.

If Deroy Murdock had talked to a “warmist,” however, he might have found out that, far from being “frigid,” last month was the hottest January on record according to global satellite measurements (the record goes back 32 years), and the fourth warmest since 1880 according to surface measurements.

The Economics of Gender Imbalance

The New York Times reports on gender imbalance on American college campuses, where women often account for as many as 55% of enrolled students. This is apparently making the few remaining men being chased by eager crowds of women, and the men hook up and cheat a lot. As explained by W. Keith Campbell, a psychology professor at the University of Georgia, which is 57 percent female: “When men have the social power, they create a man’s ideal of relationships,” which the author of the article translates as “more partners, more sex.”

Another interesting quote: “(…) the university [of North Carolina] has a high female presence in part because it does not have an engineering school.”

Meanwhile, in China lately about 54% of newborns are boys, a result presumably of selective abortions, motivated by a societal preference for male children together with the one-child policy. According to a Forbes article, this might be one of the causes of China’s extremely high savings rate, because “Wealth helps to increase a man’s competitive edge in the marriage market.”

(I found the Forbes article via a post on the excellent blog of Patrick Chovanec, a Tsinghua professor of economics. His posts on the real estate market in China and on regional differences are fascinating. Anyway, what is the mathematical mistake in his post linked above?)