Three exciting algorithmic talks at STOC'12

  1. Routing in Undirected Graphs with Constant Congestion by Julia Chuzhoy
  2. Improving Chrisofides' Algorithm for the s-t Path TSP by Hyung-Chan An, Robert Kleinberg, David B. Shmoys
  3. Multiplying Matrices Faster Than Coppersmith-Winograd by Virginia Vassilevska Williams

Oded's comments

It was the PC's idea [not mine :-)] to lump-up these three talks is a plenary session, and it was indeed an excellent idea. In fact, this session illustrates how STOC should look like: A focus on few results that are believed to deserve the attention of the entire community, and bringing the entire community together. Keeping with this spirit I have included also the third work in this choice, although it has appeared already as choice Nr 83.

The first work presents an efficient algorithm for finding ``edge disjoint'' paths with congestion $c=14$ for a given set of source-sink pairs. The solution found is within a polylog factor from the optimal, and (up to the degree of the polynomial) this is the best one can hope for. (Previously such an approximation level was only achievable for polyloglog congestion.) The algorithm is based on a new notion of relaxed embedding, and on efficiently so embedding an expander in the graph. Julia, who gave an excellent talk, concluded by announcing a recent improvement that sets $c$ to 2.

The second work refers to st-TSP which amounts to finding a path TSP between two given endpoints, as opposed to standard (circuit) TSP. For twenty years, the best known approximation, for general metric, was $5/3$ (as opposed to $3/2$ for circuit TSP), and the current work improves it to 1.6181 (the Golden ratio). The begging challenge now is to break the 3/2 barrier for circuit TSP.

The improvement in the third work is in the third digit after the decimal point but it is for (the exponent of) matrix multiplication. (See choice Nr 83.) Virginia's slides, delivered by Satish Rao, ended with ``Let's prove omega=2''...

Back to list of Oded's choices.