Email and dirty dishes

The ever-repeated quandary: is time better spent dealing with emails or actually doing work? When email exceeds my bandwidth I have a depressing accumulation mounting in my inbox, making the start of each day an ordeal. When I give priority to email, the day is spent doing small routine tasks and there is no sense of doing anything of actual value. It's a recurring problem. The problem that will not go away and that only gets worse with delays! It's like dirty dishes piling up in the sink.

It's all about notation

When designing an algorithm, one often critical step is to find a good representation for the problem input and output, that will help us think about it clearly.

When writing a proof, one often critical step is to find the right notation. Once you have decided what objects are worth having an independent notation, that will direct (or mislead) the proof.

The morale of today's lecture

Before designing an algorithm: find a good visual representation for the input and output helps you think about the problem.

Case in point: Viterbi's algorithm. Input includes so much data that it's messy to think about, until the right graph is drawn (with colors, too.)

For when the input is a permutation: represent it as a collection of points (i,sigma(i)), and hope that the output of the problem can be interpreted visually.

James Q. Wilson on liberal education

James Q. Wilson, whose existence I just learned about upon the event of his death, authored a thought-provoking essay about liberalism and liberal education. He writes:

A liberal education is at its best when it strikes this balance: when it makes one aware that principles must ultimately be justified by something more than mere utility, that liberty is as worth preserving when it is attacked by a group one admires as it is when assaulted by a group one detests, and that the bonds of civility upon which the maintenance of society depends are more fragile than we often admit.

This reminded me of the unsightly celebrations in the US a few years ago, when Saddam Hussein was executed. Sure, many people are against the death penalty... except for loathsome criminals like Saddam Hussein!

Currently, it brings to mind the preparation of the presidential campaign in France, where putative candidates must obtain the "signature" of 500 mayors before they can officially pose their candidacy (there are about 35000 mayors in the country and each mayor can give their signature to exactly one candidate.) One current question is whether the candidate for the extreme right party (the party of all prejudices) will get 500 signatures. There may be some lobbying to pressure mayors not to give her their signature, even though, in the upcoming election, it appears that she would get the votes of roughly 20 percent of the population. What is more important: to preserve the liberty of presenting candidates for all significant political parties, or to prevent the development of ideas that one detests? That is close to the dilemma presented by Wilson.

Lecturing on meta-topics

One primary goal of the Algorithms course that I am currently teaching is to teach problem-solving. That is normally done by example, going through a diverse array of algorithmic problems that come up in computer science. However, my way of teaching that has changed a little bit in recent years, with a shift to the meta-level.

Many methods I use to attack problem come without thinking. Through taking courses, reading papers, and collaborating with other researchers, I have absorbed certain ways of going about solving problems, and now I reproduce them in the hope that students will absorb them in turn. However, one of my former PhD students, Warren Schudy, systematically tried to bring out the meta-principle behind our discussions. He would be very explicit about it, reflecting aloud: "So, to no longer be stuck on this question, you are suggesting to try out some small concrete examples; that's your guiding principle" - and I would think: "Yes, of course he's right, that's what I'm doing!" Eventually I started to see the value of making explicit the guidelines that guide how we try to solve problems.

That adds a new element to my teaching: in class, I now try to not only solve the problem of the day, but also add a parenthetical comment to be more explicit about the path we took to problem-solving, the "guiding principle". It does not come naturally, since it can feel like pontificating, but it seems to have some value. Perhaps it helps demystify the "creative" steps and show that much can be achieved simply by systematically following a natural path of exploration - natural, once you have acquired enough experience to know what you're doing. I do not always remember to do it, but, following Warren's example, I try, at the end of each piece of algorithmic design or analysis, to reflect back on how we achieved it, and on the meta-tools that led us to the solution.

The New York review of books on absolute versus relative error

We usually evaluate approximation algorithms by the ratio of the output value to the unknown optimal value. Although it is almost a dogma at this point that this is the most reliable way to evaluate an algorithm, the last issue of the New York Review of Books gives an outstanding counterexample.

The article is debunking a disinformation piece published by 16 scientists in the Wall Street Journal on January 27. The WSJ misleading article was a piece of global warming skepticism.William Nordhaus establishes the fallacy of their arguments one by one. The point that caught my attention was the one about economic analysis. Nordhaus writes: The sixteen scientists argue, citing my research, that economics does not support policies to slow climate change in the next half-century, then moves on to offer the following, which can be interpreted as a beautifully clear argument against making a dogma out of approximation ratios.

The authors cite the “benefit-to-cost ratio” to support their argument. Elementary cost-benefit and business economics teach that this is an incorrect criterion for selecting investments or policies. The appropriate criterion for decisions in this context is net benefits (that is, the difference between, and not the ratio of, benefits and costs).

This point can be seen in a simple example, which would apply in the case of investments to slow climate change. Suppose we were thinking about two policies. Policy A has a small investment in abatement of CO2 emissions. It costs relatively little (say $1 billion) but has substantial benefits (say $10 billion), for a net benefit of $9 billion. Now compare this with a very effective and larger investment, Policy B. This second investment costs more (say $10 billion) but has substantial benefits (say $50 billion), for a net benefit of $40 billion. B is preferable because it has higher net benefits ($40 billion for B as compared with $9 for A), but A has a higher benefit-cost ratio (a ratio of 10 for A as compared with 5 for B). This example shows why we should, in designing the most effective policies, look at benefits minus costs, not benefits divided by costs.

The winds of change

My adult life so far has been split almost exactly 50-50 between France and the US. Now things are changing once again: I am shortly going to move back to France. While I plan to still spend a couple of months per year at Brown, in the foreseeable future I will be primarily based at Ecole Normale Superieure, in the Latin quarter in Paris.

Should anyone wish to come to Paris for a work visit, it would be a pleasure to welcome foreign visitors, collaborators, and interns.

Blogging will be light for a while, as I am occupying my time with various tedious tasks related to my move.

The year of the TSP

When I was at ITCS, last month, I talked to Huyng-Chan An who told me about his recent work with David Shmoys and Bobby Kleinberg (to appear in STOC 2012).

They study the s-t path variant of TSP, that asks for the shortest path going from a pre-specified start vertex s to a pre-specified end vertex t while visiting all other vertices along the way. What is the motivation for this problem? Well, imagine that you are a postman delivering letters. You pick up letters at the post office, deliver them, and when you're done, you go home: you have just built an s-t path, with the post office as s and your home as t. Or, imagine that your building is on fire, it is early in the morning, and the fire alarm is not working. You want to leave your office, visit all offices in the building as quickly as possible to tell anyone who might be there already that they must leave, and then you want to get out. No way you want to go back to your starting point in the end!

Christofides' algorithm, adapted to that variant, is not a 3/2 but a 5/3 approximation in the metric setting. An, Kleinberg and Shmoys have a very simple algorithm that improves the 5/3=1.66… to 1.61… The funny thing is that I did not know about the 5/3 approximation until An told me that they had improved upon that twenty years old bound! For that reason, I am hesitant to call it a breakthrough, and also because it comes along with several recent papers making progress on special cases of TSP. As a friend recently suggested, this is shaping up as "the year of the TSP"! But I looked at their result in more detail, and it is a clean, more or less self-contained, clever application of modern techniques. That's what makes it appealing.

What's the algorithm?

Nothing special, really:
(1). Solve the natural variant of the Held-Karp linear programming lower bound for TSP
(2). Express the solution as a convex combination of spanning trees (that's known to be possible by polyhedral combinatorics)
(3). Pick a random such tree T* according to the distribution given in (2), and
(4). use it in an execution of the natural variant of the Christofides heuristic.
The fact that it is "nothing special", in my view, is a good thing. It means that it can be implemented at little additional cost. (The difficulty is in the analysis.)

What's the "natural variant" of the Held-Karp constraints? Some constraints are different: every s-t cut must be crossed by a minimum of just one edge (instead of a minimum of two edges, in the usual version).

What's the "natural variant" of the Christofides heuristic? Instead of finding a perfect matching of the odd degree vertices of T*, it finds a perfect matching (T-join) of the "off-degree" vertices of T*, that is, the vertices whose degree has the wrong parity: the difference with the usual setup is that now, vertex s has the wrong parity if its degree in T* is even, and similarly vertex t has the wrong parity if its degree in T* is even.

So, that's the algorithm.

What's the analysis?

First, they present an elegant proof of the 5/3 approximation result, then modify it. Because of that, we first have to understand why the algorithm is a 5/3 approximation. The tree T* from step 3 has expected cost bounded by OPT, so the sole focus is on bounding the cost of the T-join. That is achieved by bounding the value of a particular fractional T-join. What's a fractional T-join? It's a feasible solution to the following LP:
* for every edge e, variable y(e) must be between 0 and 1
* for every proper cut (S,V-S), if S contains an odd number of "off-degree" vertices, then at least one edge crosses the cut - or in other words, fractionally, the sum, over every edge e crossing the cut, of y(e), must be at least 1.
As it happens, that polytope has integer vertices, so the optimal (integer) T-join is also an optimal fractional T-join, and so the cost of the T-join built by the algorithm in step (4) can be bounded by the cost of any fractional T-join. The proof exploits this freedom to carefully choose a particular fractional T-join whose expected cost is less than 2/3 OPT. How can it prove that the cost is less than 2/3 OPT? By proving that it's less than the 2/3 times the Held-Karp lower bound. So, the proof has now neatly moved to the realm of polyhedral analysis, and the rest is now a matter of manipulating vectors y=(y(e)).

The 5/3 result is proved by choosing, for our fractional T-join, a scaled version of an average of two solutions that each achieve the Held-Karp lower bound, namely: the fractional solution x* obtained in step (1), and the tree T* obtained in step (3). Indeed, x* satisfies all the fractional T-join constraints, but in addition, observe that there are some constraints where it has slack: for some cuts, the T-join constraint requires a weight of 1 across the cut, but x* guarantees a weight of 2 across the cut. The tree T* also satisfies all the fractional T-join constraints, but in addition, observe that there are also some constraints where it has some slack: for some cuts, the T-join constraint requires a weight of 1 across the cut, but T* guarantees a weight of 2 across the cut. Really? Well, yes: if S separates s from t and contains an odd number of "off-degree" vertices, then a straightforward counting argument shows that at last 2 edges of the tree must come out of S. Now, the funny thing is that T* has slack precisely for every constraint where x* does not have slack! So if we take the average of x* and of T*, for each constraint of the fractional T-join, we'll have (1+2)/2=3/2 edges crossing at least, and so, if we scale by 2/3, it's still feasible! That shows that y=(2/3)(x*/2+ T*/2) is a feasible fractional T-join. To recap, its cost is at most 2/3 times the average cost of x* and of T*, which is at most 2/3 OPT. The T-join built in step (4) has cost less than that, and that's how they get a 1+2/3=5/3 approximation.

How do they improve on this analysis? By fiddling with the factors cleverly. To get a fractional T-join with cost slightly better than 2/3, instead of x*/3+T*/3, they pick y=(1/3-2c)x* + (1/3+c)T*+(correction vector for the fractional T-join constraints that are now violated), and hope that the cost of the correction vector is less than c OPT. Realizing that hope requires a careful analysis of the violated constraints. They observe that
* even if constraints are violated, they're not violated by much: the sum across the cut is still at least 1-O( c). The deficiency is O( c).
* given that T* is drawn at random in step (2), those cuts are rare: an elementary argument uses Markov's inequality to show that their probability is O( c).
So the correction vector z will simply have z(e)=deficiency times Pr(e in cut where the constraint is violated) times x*(e)=O(c^2)x*(e).
Then the cost of the fractional T-join y is (2/3 - c + O(c^2))OPT, which is less than 2/3 for c small enough constant.

There's an additional technicality: the above reasoning is buggy when the violated constraints correspond to non-disjoint cuts, but they show that they can make the cuts disjoint up to introducing another small factor 1-O( c). And with that, they beat the 5/3 approximation. (There's more to the analysis to refine it and get further improvements, but that's beyond my attention span...)

What's the take-home message from that proof? Perhaps, it is a hymn to the power and flexibility of LP feasibility. The technique seems general. They pushed it through for the s-t path TSP problem, but why not use it for other problems, whenever there's an integer polytope behind the scenes?

2=1, 1=2

Two people in love: when in a romantic mood, one is tempted to think of them as two persons united by love into a single being. 2=1: a small miracle!

A woman giving birth: for those of us who don't have enough imagination to think of a child in the womb as a completely real person, what we see is that, one moment there was one person, and the next moment there were two. 1=2: another small miracle!

The Murphy's law approach to grading

Say that the assignment that you are grading is ambiguous, so that you are not sure what the students meant. One interpretation leads to a correct solution, the other one, to an incorrect solution. What to do then?

The Murphy's law approach: if something can go wrong, then it will be wrong. The student kept the writing ambiguous because he or she was not sure which specific interpretation was correct. Then, it should be counted as wrong.

But doesn't that contradict the mustard seed approach? Which approach will be taken then depends on ... on the grader's philosophy? on the grader's mood? on what he or she had for lunch? on some random coin flip, but decided consistently across all graders?