Some updates from the EURO (updated on-the-go)

Being on the EURO in Bonn, I decided to post a few pictures / impressions from the conference.

Monday, 06.07.2009:

Here are a few pictures from the opening session to start with. The morning streams were pretty empty so far (as expected?) but I suppose today’s plenary talks will be pretty well attended.

Here are two pictures from the plenary talk which were given by Reinhard Selten and Christos Papadimitriou. The first one is from Reinhard Selten’s talk on “Experimental Results on the Process of Goal Formation and Aspiration Adaptation”.

The second one is from Christos Papadimitriou’s talk on “Computing Equilibria”. He also talked about a current research project that compared genetic algorithms to simulated annealing and that came with its very own message (see the picture) 😉 :

I highly recommend the post by Mike about Christos’ talk – including the details on Christos’ question

Why do Simulated Annealing algorithms work, while Genetic Algorithms don’t?

and “Darwin’s subtle mistake”.

Tuesday, 07.07.2009:

I just learned a hell-lot about revenue management in hotels: Every day you get these small little Nik Nak’s for free. You will find them conveniently placed next to your bed so that, when waking up after a nap, you are tempted to eat them.

They look extremely innocent but they are not. Once eaten – especially if you eat those kept from the days before – you get really thirsty. I do not know how they manage to make them that salty.

You start looking around in your room and what do you find?

A bottle of water.

A bottle of water. Nothing fancy. Less than a liter. Non-carbonated. The complementary bottle of water I thought. So I took the bottle from the desk and right before opening it I saw that the lovely tag around the neck of the bottle was actually not a “welcome tag” but a price tag:

SEVEN EUROS!!!

For less than a liter of water. What is that? A mock-up of 5000%? That is the warmest welcome I had in ages!!

Hey guys, we are facing this “condition” right now. It is called recession!! That means that people do not buy water for  7 Euros when they can get a whole meal for that much money!

Today Noam Nisan (see also his report on the EURO on his blog) gave a great talk about google’s tv ad business and how they allocate the slots using game theory and ascending auctions (see his paper).

Wednesday, 08.07.2009:

The last day of the EURO 2009. Today I gave my presentation on the membership problem over the -closure for 0/1 polytopes (joint work with A.N. Letchford and A.S. Schulz). By extending Caprara and Fischetti’s 1996 result one can show that the problem remains (strongly) coNP-complete even for 0/1 polytopes. That is kind of surprising as over all the other well-known closure operators acting on 0/1 polytopes (e.g., lift and project, Sherali-Adams hierarchy, Lovász-Schrijver closures (), and Lasserre hierarchy) one can separate in polynomial time. Further Bienstock and Zuckerberg showed in 2003 that under some reasonable assumptions the more general Gomory-Chvátal closure (of fixed rank) can be approximated well in polynomial time for covering problems.

Mike Trick also gave an excellent talk today on scheduling the baseball league. The underlying scheduling problems seem to be very hard indeed. Mike told us that even for small instances – say with 12 teams – the optimal solution is still unknown and although significant research efforts the progress seems to be slow. In fact Mike is maintaining a set of instances of these scheduling problems so that you can try your luck.