Report from WADS

I just returned from WADS, formerly the Workshop on Algorithms and Data Structures but newly renamed to be the Algorithms and Data Structures Symposium, in Banff, Canada. At the conference dinner, we learned that the organizers originally intended this to be a true workshop, with 30 or so participants, but it was never that small, and the new name recognizes that. Banff National Park is beautiful; I arrived two days early with my wife Diana so that we could do some sight-seeing, and I'll be posting some photos of that part later when I catch up on my postprocessing.

Over the years I've had 14 papers at WADS, starting from the second one, at Carleton University, Ottawa, in 1991 (memorable for a conference dinner speech hoax in which the speaker pretended to be a highly skeptical politician, made fun of the titles of the papers, and wondered why the government supported research in the area). I've been to six of the eleven WADS conferences, and my papers have been to eight of them. Apparently WADS and its sister conference SWAT, with which it alternates, were the first conference series devoted entirely to algorithms (the first SWAT was in 1988, and SODA started in 1990) and this year marks its 20th anniversary. I've enjoyed all the ones I've been to, including this one; it's not as selective as SODA, maybe, but its smaller size gives it a much more personal feel.

The first day started with a bang, with a great invited talk by Erik Demaine. Erik's talk covered a lot of topics, including parallized glassblowing, mathematical origami, reconfigurable robot design, fold-and-cut paper tricks, the computational complexity of games and puzzles, simulation of arbitrary monotone Boolean functions by string and nails, and the traveling salesman artist-and-son problem, but the overall theme was that mathematics and art are one: mathematical thinking can lead to good fine art, and the quest for artistic elegance is very important in mathematical research. He provided several examples in which the process of going back and forth between writing research papers and creating examples of fine art, both involving the same topics, led to interesting breakthroughs in both directions. It would have made a great talk for a general audience, not just for the more technical WADS crowd, and it's a bit of a shame that it wasn't advertised as such in the conference program; Diana would have loved to see it, I'm sure. Fortunately, he spoke again on similar topics at the conference dinner (along with some very amusing video of rolling his father Marty around in a box decorated as a giant die) so she didn't miss all of it.

Next, I saw Maarten Löffler's talk on connecting a point to an existing road network in order to minimize the dilation of the augmented network; I wrote earlier about Maarten's talk at ACM GIS on the same problem, and this talk was similar, but covered more technical results on algorithms for performing exact optimization in this problem. I think my talk on dynamic graph statistics went well, and Allan Borodin (substituting for Joan Boyar) gave an interesting talk on a very in-depth study of a simple online algorithms problem, the two-server problem for three points on a line, showing that there can be no single algorithm that dominates the problem according to all reasonable performance metrics and pointing the way towards an Arrow-like axiomatic description of the properties we'd want a good algorithm to have. (E.g., if Algorithm A always produces a better solution than Algorithm B, we should prefer Algorithm A to Algorithm B.)

Of the two final sessions of the first day, the one I attended was on bin packing problems. Jansen, Prädel and Schwarz had a paper showing that two dimensional bin packing problems (in which one is given a collection of rectangles with side lengths at most one and must pack them into as few as possible unit squares) can be solved with an approximation ratio of 2: a better asymptotic approximation ratio is known for instances that require large numbers of bins, but the hard part seemed to be finding a way to pack rectangles into two squares whenever there exists a packing into one square. Although their algorithm runs in polynomial time, the exponent is huge (in the tens of thousands, if I recall correctly). Mike Goodrich spoke on our results on k-anonymity and bin covering, and Sandor Fekete described two algorithms with constant competitive ratios for packing an online sequence of squares of varying sizes into a strip under the "tetris" model in which one can slide squares into position from the top of the strip but, once placed, they fall downwards as far as possible.

The second day's plenary talk was by Christos Papadimitriou, on the "algorithmic lens": the idea that an algorithmic point of view can lead to fundamental progress in the classical sciences. For instance, quantum computing and Shor's algorithm for quantum factorization are providing a difficult test for physics: does quantum theory really apply to large ensembles of interacting particles, or is it only an asymptotic approximation to the true theory that works when the number of particles is small? The classical von Neumann and Nash theorems showing the existence of equilibria in games and markets provides the foundation of modern economics, but are they really meaningful in this application when complexity theory shows that equilibria may be difficult or impossible to reach? He concluded with another example that was new to me, on a subject of interest to many: sex. Specifically, what evolutionary advantage is conveyed by sexual reproduction that offsets its obvious costs (not just the costs of finding sexual partners and performing sexual reproduction, but also the evolution cost in terms of the dilution of one's genome)? Computer scientists have attempted to mimic biology, in developing genetic algorithms as heuristics for optimization problems, but these have not achieved the same success as the (asexual) simulated annealing approach to the same problems, in strong contrast to the biological success of sexual reproduction. In a PNAS paper that started out in an attempt to understand this paradox, and took the radical point of view that perhaps neither the genetic algorithm nor sexual evolution in biology lead to fitness-maximizing solutions: these solutions may be very fragile, forming sharp peaks in the fitness landscape in which variation in any dimension leads to reduced fitness. Rather, what these methods find are wide but non-optimal plateaus in the fitness landscape, in which parts of the genome are capable of supporting multiple variations that do not significantly impair fitness. Then, when the landscape changes due to population changes or external events, the organisms whose genomes extend across these plateaus are better able to respond to the changes than the organisms that are overfitted to the previous fitness landscape.

Unfortunately I had to miss what looked like very interesting computational geometry sessions on the first day (scheduled against my h-index talk) and on the second day (scheduled against Elena Mumford's talk on rectangular cartograms and my own talk on star metric embedding). The sessions I went to included several other interesting talks on graph drawing and dynamic graph algorithms, including one by Walter Didimo introducing an interesting class of graphs, those that can be drawn in the plane with straight line segments for the edges in such a way that all edge crossings are at right angles. These graphs have only linearly many edges (at most \( 4n-10 \); I think a similar bound might exist for a weaker requirement, that all crossings be at an angle strictly greater than \( 60^\circ \)) but it remains open whether they can be recognized efficiently.

After the talks of the second day I took advantage of a block of free time in the conference schedule to take a short hike with some friends from the conference, to the top of Tunnel Mountain, which has great views of the town, the Bow River, and the surrounding area. That evening was the conference “gala dinner”, a three-course buffet with live music, a trivia contest (in which I won a hat for remembering that the former Soviet republic that had hosted SWAT was Latvia), and more magic from Erik.

Sunday, the third and final half-day of the conference, was only a half-day in length, but still included some good talks. Richard Karp gave the third plenary lecture, on genomic algorithms. Most of the problems in this area are NP-complete, but exact optimization is not the point; rather, one wants to find good solutions because they are more likely to match the ground truth. His main point, which he illustrated with several examples, was that one should strive for a flexible family of approximation algorithms in which there is scope to tune the algorithm against data from the application. This time, I was able to attend the geometry contributed session (missing instead what looked like some interesting binary tree data structure talks from Bob Tarjan, Danny Sleator, and others). David Millman showed how to compute a bounded-resolution approximation to Voronoi diagrams using only low-precision arithmetic; Wolfgang Mulzer had an interesting talk on preprocessing point sets that are only approximately known so that later, once a more precise point placement is known, the Delaunay triangulation can be computed efficiently, based on the observation that a quadtree for a point set allows its Delaunay triangulation to be found in linear time via known mesh generation and Delaunay decimation techniques. Rote and Schulz showed that, if a two-dimensional body is acted on by a set of point forces that overall do not cause the body to move or spin, then there is a unique pointed pseudotriangulation having the force points as its vertices such that the body can be built as a tensegrity structure with compression elements on the interior edges of the pseudotriangulation and tension elements on the exterior. The proof involves representing the set of pointed pseudotriangulations as the vertices of a polytope and finding the correct one as a solution to a linear program. And David Charlton finished the conference with a talk on two-dimensional tree structures that can't be unfolded from their locked positions, providing examples in which the locked tree has all edges orthogonal or all with unit length; I imagine that if both orthogonality and unit length are true in the same tree, then it likely can be unfolded, but I don't know that this has been proved.

Overall, quite a successful conference; I'm glad I sent my papers there and I'm glad to have attended.

Comments: