Dagstuhl, Tuesday afternoon and Wed morning

The afternoon talks were somewhat less well attended, because the weather is so beautiful that some people just can't resist the sun and stay outside beyond the specified time.

Baruch Schieber talked some more about busy time problems. He spent some time on motivation. It's about having the minimum number of computers turned on, so, like in Kirk Pruhs' talk, it's also about minimizing power usage. It would have been nice if his talk had been before Samir's talk!

Lisa Fleischer talked about flows over time. I have heard talks about this several times, but this was the first time that I understood the problem definition before the talk was over. There's a picture of a pitcher pouring some red or blue stuff into the network. Actually, the rate at which it is pouring matches the maximum "capacity" of the edge on which things start. Also, I always think of "capacity" as a static quantity, but in this setting it's actually a rate- say, the maximum rate at which a highway can route cars without getting jammed. And time, as well as the stuff being routed, are all continuous quantities. Capacity reduction can help increase the flow. I keep thinking of those lights that regulate the rate at which cars can enter the acceleration ramp on highways at rush hours in the US. Those lights don't exist in France. I think that the French, being rational people, would not believe that you can get better overall flow by reducing input, and would therefore ignore such traffic lights. But in the US people are law-abiding enough that they stop at red lights even if it seems unreasonable.

Leah Epstein talked about online clustering problems in one dimension.

Asaf Levin talked about an asymptotic fully polynomial PTAS for bin packing with various bin sizes and costs. The techniques were a bunch of rounding/shifting/DP stuff, but the result was surprisingly strong!

In the evening we had an open problem session in the cheese room. I can't say that there was one problem that really captured my fancy, but they varied from puzzle-like to broad and ambitious questions. Then there was mafia, bridge, beer, wine, poker, and even one of the open problems was solved along the way! By a PhD student, of course: only they have the stamina to continue working at the close of the day. I noticed several people were wearing slippers.

Wednesday morning Neal Young gave a black board tutorial on Lagrangian relaxation and presented one algorithm applied to several different settings. Now it seems that I might finally be able to go back and read the Plotkin-Shmoys-Tardos paper, and it might even be easy. We'll see. Then Grigoriadis talked about non-linear approximation.