There were a couple of seminars today and one mentioned a result giving the following interesting corollary. Suppose we have a graph , and with each edge e we associate three numbers which we interpret in the following way: to construct edge e we need to use kilograms of aluminum, kilograms of beryllium, and kilograms of chromium. Later on we’ll decide to construct a spanning tree of the graph, which we would like to do cheaply; however the market price of the three metals affects which spanning tree is cheap. Nonetheless, it’s possible to fix a relatively small set of spanning trees ahead of time, and buy just one:
For k types of metals, there is a set S of spanning trees, so that for any assignment of prices to the metals, one of the spanning trees in S has minimal price among all spanning trees.
The theorem is interesting since the total number of spanning trees is exponential in . Is the theorem tight? I do not know.
The theorem follows from a more general result in the seminar (which was presented by Marco Di Summa, another member of my group at EPFL).
Take a polyhedron, and let D be the set of all directions of its edges. Then any projection of the polyhedron into k dimensions has at most vertices.
We combine this with the fact that the spanning tree polytope has at most directions (a similar fact holds for any matroid).
Three weeks ago I went back to Canada to accompany my high school on their trip to the American Computer Science League finals. Both of the teams did very well and it was a pleasure to be involved with such bright kids, not to mention the trip was a great opportunity to catch up on my StarCraft!
The past week I returned to EPFL, which was home this year to the 14th conference on Integer Programming & Combinatorial Optimization. Inspired by my colleague Cora’s recent display of statistical information, I decided to keep track of what programs people used to give their presentations, and where possible, the number of slides. Out of 34 talks, 18 were in beamer, 3 were in keynote, 4 were in some other type of LaTeX, 6 were in powerpoint, and 3 I could not classify.
Here is the data on the length (in slides), where it was available:
Talk Length by Format
I found that my 21 slides fully used up the 25-30 minute time period for the talk, although I also saw a 13-slider and a 38-slider which were very well timed. What’s the difference between these talks? More information per slide? Am I a fast-talker or a slow-talker? At least I don’t think I am a close-talker.
My talk (joint with Deeparnab Chakrabarty and Jochen Könemann who was my PhD advisor) was on linear programming relaxations for the Steiner Tree problem. The central idea is to take the “full component” method which has underlied most algorithmic progress on the problem for the last 20 years, and use it with linear programming. We found a large number of previously unnoticed links between existing work, and proposed a couple of algorithms whose analysis provide quantified lower bounds on the strength of the relaxation.
I defended my PhD thesis one week ago! (Successfully!) Although I am not finished until I complete my thesis revisions, being past the most stressful 2 hours is excellent and I enjoyed getting to see some talks from visitors on the same day.
Other epic wins:
I got to visit Pittsburgh’s Carnegie Mellon University 2 weeks ago to visit my old friend Andrew and give a talk at the CS Theory Lunch (free burrito included)
The UW Grad Student Association website no longer needs to be manually updated every time we leap ahead/fall back for Daylight Savings Time thanks to WordPress being awesome and a few minutes of additional php hacking on my part
Saw a holiday brass concert and some roof-based fiddling in Toronto last week, the first play I have seen in quite a long time. According to Wikipedia, the original Fiddler ran more than 3000 times! I get bored of doing something three times…
Epic fail: I lost one glove over the weekend! Have you seen it?
I got to see a couple of good talks today by other students at Waterloo.
First, my roommate Igor gave his Master’s thesis presentation. His talk was centered around finding dominating sets in Kneser graphs, and generalizations. Many of his results were summarized in a table regarding upper and lower bounds. A single entry of the table required a complicated case analysis (namely, that a dominating set of the 9:3 Kneser graph has at least 7 vertices)… it reminds me of the search for Ramsey numbers, and I was glad to hear during the talk that most of the other hundred-or-so entries didn’t each require so much attention; otherwise I doubt that I would ever have seen him leave his room…
The second talk was by Mustaq Ahmed of the computer science department. The basic problem he considered is pretty natural: given a terrain, what is the shortest path from point A to point B that never goes uphill? For example, what is the shortest path to ski down a mountain, or the minimum length of aqueduct needed for irrigation from the a glacier to the fields below. To analyze the problem one models the terrain by a polyhedron (e.g., planar faces joined at straight lines); the talk had lots of interesting snippets dealing with convex optimization, approximation algorithms, and Steiner points. There’s a related problem that appears to be very popular:
You are “the amazing mr. sticky-fingers,” and you are sitting in one corner of a 10x10x10 metre room. What’s the shortest path (including climbing walls and/or ceilings) to get to the opposite corner (the one where the far two walls meet the ceiling)?
Anyway, the answer to this problem is pretty nice, but it is apparently unknown yet whether exact solutions for similar “downhill-only” problems have a closed form.
One of today’s conference talks was excellent. It was by Alex Schrijver, entitled Graph and Knot Invariants; this was the first time I’ve seen him talk.
Top five reasons I liked this talk:
5. Schrijver is best known (I think) for his work in combinatorial optimization (including a 3-book series that spans the whole discipline) and even though this talk was outside of that field it was still pimptacular.
4. Used overheads better than most people use powerpoint: he had layering effects and used two projectors to keep a cache of information visible, which was helpful. Also, sweet diagrams.
3. Gave graph-theoretic motivation for algebra (the whole talk, basically) and algebraic motivation for graph theory (characterizing invariant rings on group algebras).
2. The main results were clean and mysterious and apparently have elegant proofs. Plus, you could actually understand what he was talking about for most of the talk.
1. Talk contained phrase “keep it real” (in reference to not using complex numbers).
My department, Combinatorics and Optimization, is hosting a conference this week in honour of its 40th anniversary. So things are about to get a little more nerdy on this blog as I will be mentioning some of the talk details.
For today, at least: a picture! (click for big-ass pdf)
It’s my contribution for today’s poster session. Now it’s time to go get free conference coffee, yum!
Update: the first talk of the morning was by Richard Stanley; not a household name perhaps (who is anyway? — Perelman and Wiles?) but the organizers evidently wanted to motivate people to wake up and go to the morning session. His alternating partition survey had a number of interesting results, including the following.
Shuffle a large deck of cards numbered 1 to and look at the first card. Then, for each of the remaining n-1 cards, flip it over and say if it is higher (H) or lower (L) than the previous. The most likely sequences of H’s and L’s are HLHLHLHL… and LHLHLHLH… .
In comparison, for example, the sequence HHHHHH… is very unlikely and can only occur when the cards are sorted into increasing order by the shuffle.
I saw a talk today with (for once!) some useful advice. It was by Bala Ravikumar and he discussed Benford’s law, which says that in “real life” the first digit of numbers tend to be small. (Benford’s law basically says that the distribution of miscellaneous data is uniform on a logarithmic scale. On a logarithmic scale, e.g., the range [1.0, 1.999…] is several times as large as the range [9.0, 9.999…]) More specifically, he noted that tax fraud has previously been detected in people whose tax numbers didn’t confirm to the law.
So… if you feel like faking a tax return, make sure about 30% of your numbers start with a “1” and only 4.5% start with a “9”!
In other news, I gave a talk today which I developed out of a previous “better know a theorem” post; the talk is here. I was punked in the Q&A question by Jim Geelen 😦 who pointed out that integer linear equality systems can be solved in P-time, essentially, using Gaussian elimination (although then he mumbled something about a Hilbert basis).
Bill Cook gave a talk at Waterloo about some of his work on the Traveling Salesman Problem (TSP). He has worked in the area for something like two decades. Here are some notes and highlights of his talk.
One of his main research interests is the solution of TSPs to optimality. It’s worth pointing out that many traditional applications are interested in getting cheap solutions, which many approximation algorithms will give you; so then why should we bother to solve for the cheapest solution (which is potentially much computationally harder, since TSP is NP-complete)? He gave one recent example of radiation hybrid genome sequencing where the exact optimum is needed, and his work has been used to improve clinical sequencing operations.
Recently (with some colleagues) he was able to solve the largest unsolved TSPLIB instance to optimality; it had about half a million cities. It took many computer-years of time; for this reason he stressed the importance of having a method to independently verify the optimality of the computation’s result. However, by cleverly extracting the appropriate “certificates,” the optimality of the best solution can be verified in just about 12 hours of computer time.
He also pointed out that the CPLEX “default optimality tolerance” is about 0.0001%, and that if a user were unaware of this, they could easily find an “optimal” solution to an IP which is actually non-optimal. Along these lines, he described some details of how he is working on an exact-arithmetic LP solver for use in his work. There was some mention that exact linear solving of sparse systems (e.g., Wiedermann’s method) would be useful in part of his work.
spanning trees, so that for any assignment of prices to the metals, one of the spanning trees in S has minimal price among all spanning trees.
vertices.
QED and NOM 