I just saw the video of a talk by Mohit Singh presenting the TSP result discussed on the Fortnow-Gasarch blog a few months ago.
The input is the metric given by shortest paths in an undirected unweighted graph. The output is a traveling salesman tour with length less than
OPT*1.4999999999999999999999999999999999999999999999999996.
Ever since my student days, I have heard of this - beating the factor of 1.5 for metric TSP - as a major open problem. I even spent some time working on this as a young graduate student, under Andy Yao's guidance (and with no luck whatsoever), so this is exciting, even if it's restricted to graph metrics.
The plan follows the Christofides algorithm, but finds a particular MST such that the minimum weight matching of odd degree vertices is a better than .5 approximation. The algorithm studies the following two LP relaxations:
First, the Held-Karp LP relaxation of TSP, LP1: minimize the sum of d(u,v)x(u,v), where for every vertex u the sum over v of x(u,v)=2, and for every cut, the sum over cut edges {u,v} of x(u,v) is at least 2. Here x(u,v) is non-negative.
Second, given a spanning tree T, the following LP relaxation to build a minimum weight perfect matching over vertices that have odd degree in T, LP2(T): minimize the sum of d(u,v)y(u,v), where for every cut crossed by an odd number of edges of T, the sum S over cut edges {u,v} of y(u,v) is at least 1. Here y(u,v) is non-negative.
It is known that the minimum spanning tree has value less than OPT(LP1), which is less than the OPT tour. It is known that the minimum weight perfect matching of odd degree vertices has value exactly equal to OPT(LP2(T)). Observe that if x is feasible for LP1, then for every T, y=x/2 is feasible for LP2(T), so OPT(LP2(T)) is at most (1/2)OPT(LP1). This proves the 1.5 bound of Christofides.
Now, here is the first idea: imagine that instead of defining y(u,v) as x(u,v)/2, we defined it as x(u,v)/(2.001). Would this still be feasible for LP2(T)? Yes, if for every cut that contained edge {u,v}, either the sum S was greater than 2.001, or the cut was crossed by an even number of edges of T. If we could find such a minimum spanning tree T, then OPT(LP2(T)) would be less than (1/2.001)LPT(LP1) and we'd have a better-than-1.5 approximation.
Studying OPT(LP1), the authors can show that (except for the special case when the solution of LP1 is near integral, dealt with separately) for a significant number of edges called "good" edges, the number of cuts containing that edge and such that the sum S is less than 2.001 is bounded by a constant c. So all we need is a tree T such that for many of those edges, every one of the c cuts of interest is crossed by an even number of edges.
Unfortunately it is difficult to construct a tree T having such a nice property, so instead, (as in the SODA 2010 paper by Asadpour, Goemans, Madry, Gharan and Saberi) the authors pick a random tree from the following distribution: there exists a unique distribution of trees s.t. for each edge uv, the probability that uv is in the tree is x(u,v), and such that for every tree T, the probability of T is proportional to the product of x(u,v) for each edge uv of T. In fact, that's the weighted uniform distributon defined as follows: scale the x's up so that they're all integers, replace the graph by a multigraph where each edge {u,v} is replaced by x(u,v) identical edges between u and v, then generate a uniform spanning tree of the resulting graph. Consider the random tree T thus obtained.
It only remains to study, for each good edge, the probability that all c cuts of interest are crossed by an even number of edges of T. For each edge {u,v}, the probability that the edge is in T is x(u,v). For each set of k edges, the probability that all of those k edges are in T is known to be given by a certain determinant. A lot is known about weighted uniform spanning trees. The very vague intuition is that if the average number of edges crossing a cut is between 2 and 2.001, since the weighted spanning tree distribution is very roughly similar to picking edges independently at random (except for the tree constraint...), there is a significant probability that the number of edges crossing the cut will be, not 1, not 3, but exactly 2. Since 2 is even, we're in good shape.
It is beautiful how this puts together techniques from the study of linear programs, and recent advances on random trees and discrete probability.
Tuesday, June 21, 2011
Monday, June 20, 2011
Dropbox, svn, and self-discipline
Applications such as Dropbox or svn help me work on papers with my coauthors. It allows us to edit our paper in parallel, with frequent (or even automatic and transparent, in the case of Dropbox) updates to the common repositary that ensures continued consistency. In the old days, we used to email our draft back and forth, with message headers such as: "I am taking the token on the paper. Let no one else edit it!" and "I am now releasing the token". Instead, Dropbox saves us the work of coordinating our schedule and jointly planning when each of us is going to edit the paper. It gives us a lot more freedom.
But here is something I noticed the other day. I was editing a draft, went through about three quarters of it, then when I got tired of editing, I stopped and updated the repositary.
In the old days, I would have pushed myself and finished editing before releasing the token.
In the old days, when conference deadlines were approaching, we had to be very organized to synchronize our work so as to be done in time. Now each author can work more or less independently from the others, and the observed effect is that people wait until much closer to the deadline.
In the old days, writing a paper used to happen in waves: we'd write a first draft, then correct it to make a second draft, then go over it once or twice more at most, and then we'd call it good enough for submission. Now there is no sense of "version number i": the draft is updated continuously, and it can never really be said to be finished. Further improvements are always possible.
So in the old days, there were many synchronization constraints that forced us to be organized, or else the cost was high: one small misstep often meant that a whole day was lost. Now things are much more robust: missteps can be corrected instantaneously, so the cost of making mistakes is low, and careful planning is no longer necessary. Instead can almost entirely live in the present. We have enormously more freedom.
What is the result? One result is that I currently have a large number of drafts in various stages of being close to completion. When I am 3/4 done and feel a bit tired, there is no reason not to stop. Moreover, I am reluctant to call a paper "ready for submission", since there is always one more small improvement that is possible and easy to make.
More freedom, unless coupled with more self-discipline, results in decreased efficiency.
But here is something I noticed the other day. I was editing a draft, went through about three quarters of it, then when I got tired of editing, I stopped and updated the repositary.
In the old days, I would have pushed myself and finished editing before releasing the token.
In the old days, when conference deadlines were approaching, we had to be very organized to synchronize our work so as to be done in time. Now each author can work more or less independently from the others, and the observed effect is that people wait until much closer to the deadline.
In the old days, writing a paper used to happen in waves: we'd write a first draft, then correct it to make a second draft, then go over it once or twice more at most, and then we'd call it good enough for submission. Now there is no sense of "version number i": the draft is updated continuously, and it can never really be said to be finished. Further improvements are always possible.
So in the old days, there were many synchronization constraints that forced us to be organized, or else the cost was high: one small misstep often meant that a whole day was lost. Now things are much more robust: missteps can be corrected instantaneously, so the cost of making mistakes is low, and careful planning is no longer necessary. Instead can almost entirely live in the present. We have enormously more freedom.
What is the result? One result is that I currently have a large number of drafts in various stages of being close to completion. When I am 3/4 done and feel a bit tired, there is no reason not to stop. Moreover, I am reluctant to call a paper "ready for submission", since there is always one more small improvement that is possible and easy to make.
More freedom, unless coupled with more self-discipline, results in decreased efficiency.
Sunday, June 19, 2011
On Lecturing: introduction
I just read a document that I think can be interpreted via the lens of teaching. Instead of bits and pieces of observations about teaching, it gives a general framework. Here is the beginning of my attempt to cast it in that light.
Classes are an essential part of the student's education. We need to be effective lecturers. There are three elements coming together: the scientific content (the result or technique that we wish to teach), the teacher, and the students. Effective teaching requires us to know our students, so that we can communicate to them what they are ready to learn. If we are not in touch with our students' current level of understanding, what we say will not be heard. Our students' diverse level is a challenge. Many students have an intuitive understanding of problem-solving, but are unable to articulate it rigorously, and one of our tasks is to provide them with a vocabulary to express their concepts and refine them. When the students are presented with a scientific publication, usually it does not "talk to them". Our role is to be the mediator between the scientific content and the students, interpreting it so that it reaches another level of meaning for them.
Classes are an essential part of the student's education. We need to be effective lecturers. There are three elements coming together: the scientific content (the result or technique that we wish to teach), the teacher, and the students. Effective teaching requires us to know our students, so that we can communicate to them what they are ready to learn. If we are not in touch with our students' current level of understanding, what we say will not be heard. Our students' diverse level is a challenge. Many students have an intuitive understanding of problem-solving, but are unable to articulate it rigorously, and one of our tasks is to provide them with a vocabulary to express their concepts and refine them. When the students are presented with a scientific publication, usually it does not "talk to them". Our role is to be the mediator between the scientific content and the students, interpreting it so that it reaches another level of meaning for them.
Saturday, June 18, 2011
An advanced search
The other day I was looking for the text of the 1940 French-German armistice in the original German language (don't ask). How could I find it without knowing any German? Here is how I did it:
1. I opened google, my default search engine, and entered the keywords "1940 French German armistice original German text". Among the answers, I did not see the German original, but there was an English translation.
2. I used google translate to translate the words "1940 French German armistice original German text" into German.
3. I entered the resulting string of German words back into google search.
4. Among the answers, there was a wikipedia page: I clicked on it.
5. It was in German, so I could not understand a word of it, but it ended with some references, as wikipedia pages usually do, and I clicked on the first reference.
6. What I saw then was the scan of a text in German, with paragraphs labeled 1 through 24. Since I could see, from the English translation, that the armistice text was supposed to have 24 items, I knew I had found what I was looking for.
I am so proud of myself.
Now, the next challenge: a Japanese text?
1. I opened google, my default search engine, and entered the keywords "1940 French German armistice original German text". Among the answers, I did not see the German original, but there was an English translation.
2. I used google translate to translate the words "1940 French German armistice original German text" into German.
3. I entered the resulting string of German words back into google search.
4. Among the answers, there was a wikipedia page: I clicked on it.
5. It was in German, so I could not understand a word of it, but it ended with some references, as wikipedia pages usually do, and I clicked on the first reference.
6. What I saw then was the scan of a text in German, with paragraphs labeled 1 through 24. Since I could see, from the English translation, that the armistice text was supposed to have 24 items, I knew I had found what I was looking for.
I am so proud of myself.
Now, the next challenge: a Japanese text?
Friday, June 17, 2011
Who to kiss when
The other day, here in the US, a man came to my house to be paid for some work he did in my yard. We chatted for a few minutes, then, as he was taking his leave, he unexpectedly kissed me on the cheek.
Later I realized the reason behind his action: he knew that I was French and that the French greet one another by kissing, and he wanted to thus show his knowledge of the world!
What he did not know is that we French women do not kiss our painters, plumbers, electricians, or gardeners, -- unless they happen to also be our friends of course. Otherwise, the proper protocol is to shake hands.
Many Americans, when they are in France, enthusiastically kiss everyone in sight. Not so fast! The boundary between who gets a handshake and who gets a kiss can be subtle. The first time it happens, we make eye contact: one person silently says with their eyes: "I think we have reached the stage in our acquaintance where we can now kiss instead of shaking hands, don't you agree?", and the other person silently assents. When there is any risk of ambiguity, the first person will smile and tentatively ask: "On se fait la bise?", but it would be quite embarrassing if the other person said no, so, if there is any doubt, the safe route is to go for a handshake.
I would say that the people who get a kiss are: family, except perhaps for remote extended family when met for the first time; friends; friends of friends, if they are introduced to us by our friends and if the context is not too formal; acquaintances and colleagues, once a casual friendship starts to develop; and all children. I don't make a difference between blood relatives and other relatives, but some people only kiss the relatives who share some of their genes. I don't kiss my pastor, out of residual respect for some remnant of tradition of authority that he symbolizes, but some people do. The older people are, the more hesitant I am to go for a kiss, and the more I wait for their cue. There are people with whom I go both ways, exchanging either a kiss or a handshake, depending on how formal the context is when we meet. No one I know kisses their garagist, supermarket cashier, or children's schoolteachers. But the boundary is subtle and, I think, very much depends on one's social class.
UPDATE: Here's a simple rule: do not kiss anyone whom you would not befriend on Facebook!
Later I realized the reason behind his action: he knew that I was French and that the French greet one another by kissing, and he wanted to thus show his knowledge of the world!
What he did not know is that we French women do not kiss our painters, plumbers, electricians, or gardeners, -- unless they happen to also be our friends of course. Otherwise, the proper protocol is to shake hands.
Many Americans, when they are in France, enthusiastically kiss everyone in sight. Not so fast! The boundary between who gets a handshake and who gets a kiss can be subtle. The first time it happens, we make eye contact: one person silently says with their eyes: "I think we have reached the stage in our acquaintance where we can now kiss instead of shaking hands, don't you agree?", and the other person silently assents. When there is any risk of ambiguity, the first person will smile and tentatively ask: "On se fait la bise?", but it would be quite embarrassing if the other person said no, so, if there is any doubt, the safe route is to go for a handshake.
I would say that the people who get a kiss are: family, except perhaps for remote extended family when met for the first time; friends; friends of friends, if they are introduced to us by our friends and if the context is not too formal; acquaintances and colleagues, once a casual friendship starts to develop; and all children. I don't make a difference between blood relatives and other relatives, but some people only kiss the relatives who share some of their genes. I don't kiss my pastor, out of residual respect for some remnant of tradition of authority that he symbolizes, but some people do. The older people are, the more hesitant I am to go for a kiss, and the more I wait for their cue. There are people with whom I go both ways, exchanging either a kiss or a handshake, depending on how formal the context is when we meet. No one I know kisses their garagist, supermarket cashier, or children's schoolteachers. But the boundary is subtle and, I think, very much depends on one's social class.
UPDATE: Here's a simple rule: do not kiss anyone whom you would not befriend on Facebook!
Thursday, June 16, 2011
"It talks to you"
The contractor repainting my house told me that, to find potential problems with the house, you look at the siding and "you've got to let it talk to you". You stare at the shingles and "they talk to you": chipped corner, darker stain, soft wood, insect holes, faded colors. They're all symptoms of a variety of problems. You see the problems, put two and two together, and figure out where they come from.
What he described was an approach to problem-solving that can readily be applied to mathematical problems. You look at a series of examples. You stare at them attentively, you let them "talk to you", and the structure of the problem comes through.
What he described was an approach to problem-solving that can readily be applied to mathematical problems. You look at a series of examples. You stare at them attentively, you let them "talk to you", and the structure of the problem comes through.
Wednesday, June 15, 2011
"Is it a good idea to..."
That's how I was starting a query into my search engine with the idea of exploring the pros and cons of students borrowing money to pay for college. I got stopped in my tracks by the automatic completions proposed by the search engine:
-Is it a good idea to microwave an airbag?
-Is it a good idea to lease a car?
-Is it a good idea to join the marines?
-Is it a good idea to get back with your ex?
-Is it a good idea to invest in gold?
Now I can't stop staring at them. Microwave an airbag?!?? These automatic completions of search queries offer amazing snapshots of the public mind.
And here's the big question: what does it all mean? If the first thing an internet user is wondering about is whether to microwave an airbag, is it a sign that this society is bored to death?
UPDATE: I changed my search settings to turn off the automatic completion option. It's fun, but very distracting!
-Is it a good idea to microwave an airbag?
-Is it a good idea to lease a car?
-Is it a good idea to join the marines?
-Is it a good idea to get back with your ex?
-Is it a good idea to invest in gold?
Now I can't stop staring at them. Microwave an airbag?!?? These automatic completions of search queries offer amazing snapshots of the public mind.
And here's the big question: what does it all mean? If the first thing an internet user is wondering about is whether to microwave an airbag, is it a sign that this society is bored to death?
UPDATE: I changed my search settings to turn off the automatic completion option. It's fun, but very distracting!
Tuesday, June 14, 2011
Fighting internet addiction
At my house, we are experimenting with a new rule to fight internet addiction: no internet connection between 10pm and 7am. It is very easy to implement since it's just a matter of switching a button. It has the immediate consequence that we get more sleep. It's a measure of how much we rely on the internet that it has taken some discussion and required an effort of will.
I suppose that that could be embedded in Verizon, Cox, and other internet service providers. They could give us an option to have a subscription that excludes nights and Sundays, for example.
I suppose that that could be embedded in Verizon, Cox, and other internet service providers. They could give us an option to have a subscription that excludes nights and Sundays, for example.
Monday, June 13, 2011
The cost of tuition
This is the cost of tuition at Brown University: nominal, and, in parenthesis, inflation adjusted (2010 dollars)
2011 $41328 (not yet known)
2010 $39928 ($39928)
2009 $38048 ($39469)
2008 $36828 ($37267)
2007 $35584 ($37377)
2006 $33888 ($36592)
2005 $32864 ($36373)
2004 $30672 ($35101)
2003 $29200 ($34520)
2002 $27856 ($33556)
2001 $26568 ($32773)
2000 $25600 ($32084)
1999 $24624 ($31910)
Does this mean that this college has become more money-elitist, restricting admission except to the wealthy?
At the same time financial aid has increased from $34 millions in 2002 ($40 millions inflation adjusted dollars) to $81 millions in 2010, thus basically doubling. Does this mean that this college has become less money-elitist, redistributing more income so as to provide admission to the less wealthy as well?
If we take this to the limit, the tuition could be set at infinity, financial aid could be at near-infinity, and the financial aid office could decide arbitrarily how much each student has to pay out of their own pocket. The main result is that the college has more control over who pays what. That is, those numbers are reflecting reality less and less.
2011 $41328 (not yet known)
2010 $39928 ($39928)
2009 $38048 ($39469)
2008 $36828 ($37267)
2007 $35584 ($37377)
2006 $33888 ($36592)
2005 $32864 ($36373)
2004 $30672 ($35101)
2003 $29200 ($34520)
2002 $27856 ($33556)
2001 $26568 ($32773)
2000 $25600 ($32084)
1999 $24624 ($31910)
Does this mean that this college has become more money-elitist, restricting admission except to the wealthy?
At the same time financial aid has increased from $34 millions in 2002 ($40 millions inflation adjusted dollars) to $81 millions in 2010, thus basically doubling. Does this mean that this college has become less money-elitist, redistributing more income so as to provide admission to the less wealthy as well?
If we take this to the limit, the tuition could be set at infinity, financial aid could be at near-infinity, and the financial aid office could decide arbitrarily how much each student has to pay out of their own pocket. The main result is that the college has more control over who pays what. That is, those numbers are reflecting reality less and less.
Sunday, June 12, 2011
Marketing a paper
As I am reading the book "Influence" about marketing and manipulation, I am wondering if that's of any relevance to writing papers.
One of the first points is the efficiency of trying to push onto the client, first, something that he will probably refuse, then, something more acceptable. Compared to starting right off with the final suggestion without the preliminary phase, this is much, much more successful (for some experiements the success rate goes from 20% to 50% or so). Can we imagine something similar for marketing a paper?
For example, in the introduction, to present the results it might be a good strategy to first expose the weaker results. The reviewer, reading that, thinks: "Well, this paper is not good enough to be accepted" -- but then, at the end of the introduction, suddenly, here come significantly stronger results. Then the reviewer might think: "Wow. This paper is actually much stronger than I thought at first!" Is this a better marketing strategy than starting right off with one's main result?
I must say that it goes against the way in which I write, the way in which my coauthors write, and the way in which I teach my students to write. I always try to go for the straightforward statement, going to the main point as quickly and with as much clarity as possible. But if I believe this book, it is possible that papers that put more thought into the marketing perspective are much more successful at selling themselves, independently of the results themselves and of how well the paper is written from terms of readability, clarity, etc. That's a disturbing thought!
One of the first points is the efficiency of trying to push onto the client, first, something that he will probably refuse, then, something more acceptable. Compared to starting right off with the final suggestion without the preliminary phase, this is much, much more successful (for some experiements the success rate goes from 20% to 50% or so). Can we imagine something similar for marketing a paper?
For example, in the introduction, to present the results it might be a good strategy to first expose the weaker results. The reviewer, reading that, thinks: "Well, this paper is not good enough to be accepted" -- but then, at the end of the introduction, suddenly, here come significantly stronger results. Then the reviewer might think: "Wow. This paper is actually much stronger than I thought at first!" Is this a better marketing strategy than starting right off with one's main result?
I must say that it goes against the way in which I write, the way in which my coauthors write, and the way in which I teach my students to write. I always try to go for the straightforward statement, going to the main point as quickly and with as much clarity as possible. But if I believe this book, it is possible that papers that put more thought into the marketing perspective are much more successful at selling themselves, independently of the results themselves and of how well the paper is written from terms of readability, clarity, etc. That's a disturbing thought!
Subscribe to:
Posts (Atom)