Report from FUN

I've been in Venice the last few days, for the 6th International Conference on Fun with Algorithms. It's a beautiful city, the conference location (the small island of San Servolo, a short boat ride from the city) is also beautiful, the local organizers have been very helpful at guiding us through the city, and we've been served some amazing seafood here.

On the first day, I gave my own talk on algorithms that try to replicate imprecise human-style Sudoku reasoning rather than (as is more usual for algorithms) directly trying to find an optimal solution. I've written on this in more detail here, and I've now put my talk slides on the web.

The conference lived up to its name, and there were too many good and entertaining talks for me to mention all of them, so let me just add a few words about some that I found particularly intriguing, in no particular order.

Giuseppe Persiano gave the first invited talk about what happens in game theory when one assumes that each players' choices are drawn randomly from some distribution (proportional to an exponential function of their utilities) rather than assuming perfect rationality (in which each player always takes the utility-maximizing option). This model turns out to shed light on the dynamics of consensus in social networks (e.g. everyone using Facebook because everyone else uses Facebook). Relatedly, I noticed that almost everyone at the conference used pdf format for their talk slides; there were some Powerpoint and Keynote presentations, but not many. And Jinyun Yan's talk (on what insights can be gained from looking at the source code of arXiv papers) showed some interesting divergences between the two consensuses of mathematicians and computer scientists on what LaTeX packages to use for papers.

Jorge Urrutia gave an inspiring invited talk on the second day concerning variations of the art gallery problem when the guards (or more realistically wireless modems) can see through a limited number of walls. One of his problems, the question of how many walls one needs to be able to see through to guard a gallery with only a single guard, turns out to be equivalent to regression depth.

I learned from Jyrki Katajainen that perfectly balanced binary trees and perfect medians as pivots in quicksort are not actually optimal. In the presence of branch prediction hardware (in a language like C that is close enough to the hardware), one can do a little better to pick asymmetric pivots and asymmetric tree roots, in order to make the algorithm's branches more predictable.

Both Erik Jan van Leeuwen and Kitty Meeks spoke about certain graph optimization problems that are NP-hard on trees, but nevertheless can be solved efficiently on some interesting classes of graphs (that, obviously, do not include all trees) It made me wonder about what the largest "reasonable" such classes might be. A minor-closed class of graphs does not include all trees if and only if it has bounded pathwidth, so looking for FPT algorithms on bounded pathwidth graphs looks like a reasonable thing to try. But Meeks described an algorithm for graphs with polynomial numbers of connected subgraphs; in the minor-closed case this seems to be equivalent to considering minor-closed graph families of bounded degree, or the graphs in which each connected component is a subdivision of a graph in some finite set of model graphs.

Among the algorithms presented, the one with what seems the greatest likelihood of practical usefulness was presented by Gerhard Woeginger, and concerned a model of fair allocation of indivisible objects (pieces of property in a divorce, say) given only combinatorial information about the preferences of the parties dividing the objects. They give a simple algorithm for performing such a division in such a way that (whenever it is possible) both parties are convinced that they got at least half the total value. Runner-up for usefulness was a paper by Kevin Lang on efficiently generating permutations by selecting weighted items one at a time without replacement; an \( O(n) \) algorithm was known, and his algorithm is \( O(n \log\log n) \) in the worst case, but it's fast and much more implementable than the previous one.

---

Comments: