Report from Algo 2009

I just returned from ALGO 2009 in Copenhagen.

Algo is composed of ESA — the main European algorithms conference — co-located

with a few smaller workshops.  ALGO had about 200 participants mostly from Europe but from other places as well (As usual a bunch of Israelis and also

I met a significant number of

attendees from China: from Tsinghua and Fudan universities, and from Microsoft Reserach in Beijing.)  The acceptence rate for papers sumitted to ESA was about 25%.

The social program included a dinner in Tivoli garden and a (perfectly engineered) bike ride throug the streets of Copenhagen.

X and Y already blogged about ESA so I’ll just mention the AGT sessions (even though I arrived late and missed them):

<ul>

<li>Yossi Azar, Benjamin Birnbaum, Anna Karlin and Thach Nguyen. On Revenue Maximization in Second-Price Ad Auctions.

<li>Mohammad Mahdian and Grant Wang. Clustering-Based Bidding Languages for Sponsored Search.

<li>Martin Hoefer and Alexander Skopalik. Altruism in Atomic Congestion Games.

<li>Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang and Jiajie Zhu. Bounded Budget Betweenness Centrality Game for Strategic Network Formations.

<li>Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation.

<li>George Christodoulou, Elias Koutsoupias and Paul Spirakis. On the performance of approximate equilibria in congestion games.

</ul>

Additionally, two invited talks were related to AGT: my own talk on Google’s auction for TV ads (paper, slides), and Vijay Vazirani’s talk

on combinatorial algorithms for market equilibrium and for the Nash bargaining solution.  Both of these problems (in some variant) can be described

by convex optimization programs that are surprisingly very similar to each other: the “market clearing conditions” are linear constraints and the optimization

goals are, respecitevly, of the form and .  While these can be solved in polynomial time by

general comvex programming, Vijay called for, and discovered, combinatorial algorithms that shed more light on the structure of these problem.

Vijay’s market equilibrium model was the continuous analog and inspiration of the discrete one that underlines the auction for TV ads that I presented, so

I was naturally quite interested.

I just returned from ALGO 2009 in Copenhagen.    AlGO is composed of ESA — the main European algorithms conference — co-located with a few smaller workshops.  ALGO had about 200 participants mostly from Europe but from other places as well (I met a significant number of  attendees from China: from Tsinghua and Fudan universities, and from Microsoft research in Beijing.)  The acceptance rate for papers submitted to ESA was about 25%. The social program included a dinner in Tivoli gardens and a (perfectly engineered) bike ride through the streets of Copenhagen, and the whole affair was quite enjoyable.

Others (here and here) have already blogged about ESA so I’ll just mention the AGT sessions (even though I arrived late and missed them):

1. Yossi Azar, Benjamin Birnbaum, Anna Karlin and Thach Nguyen. On Revenue Maximization in Second-Price Ad Auctions.
2. Mohammad Mahdian and Grant Wang. Clustering-Based Bidding Languages for Sponsored Search.
3. Martin Hoefer and Alexander Skopalik. Altruism in Atomic Congestion Games.
4. Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang and Jiajie Zhu. Bounded Budget Betweenness Centrality Game for Strategic Network Formations.
5. Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation.
6. George Christodoulou, Elias Koutsoupias and Paul Spirakis. On the performance of approximate equilibria in congestion games.

Additionally, two invited talks were related to AGT: my own talk on Google’s auction for TV ads (paper, slides), and Vijay Vazirani’s talk on combinatorial algorithms for market equilibrium and for the Nash bargaining solution.  Both of these problems (in some variant) can be described by convex optimization programs that are surprisingly very similar to each other: the “market clearing conditions” are linear constraints and the optimization goals are, respectively, of the form and .  While these can be solved in polynomial time by general convex programming, Vijay called for, and discovered, combinatorial algorithms that shed more light on the structure of these problem. Vijay’s market equilibrium model was the continuous analog and inspiration of the discrete one that underlines the auction for TV ads that I presented, so I was naturally quite interested.

Advertisement