Algorithmic Game Theory and Metric Embeddings (original) (raw)
Relations with Computer Science: Algorithmic Game Theory and Metric Embeddings
July 4-6, 2005, Santander, Spain.
This is one of 20 workshops that make up the FoCM 2005 conference. The focus of this workshop is on Algorithmic Game Theory and Metric Embeddings, two areas in which Computational Mathematics and Computer Science have close connections. A third theme of this workshop is Approximation Algorithms, a central topic in computer science that is closely related to both of these areas.For local and conference information, see the conference webpage.
ORGANIZERS:
- Allan Borodin (University of Toronto)
- Avrim Blum (Carnegie Mellon University)
TENTATIVE SCHEDULE:
July 4:
| Block 1 [1:50-2:35] | Yossi Azar The Price of Routing Unsplittable Flow |
|---|---|
| Block 2 [2:40-3:25] | Kamal Jain An application of market equilibrium in distributed load balancing in wireless networking |
| BREAK [3:25-4:00] | COFFEE BREAK |
| Block 3 [4:00-4.45] | Berthold Voecking [SEMI-PLENARY] Approximation Techniques for Utilitarian Mechanism Design |
| Block 4 [4.50-5.35] | Jason Hartline Derandomization of Auctions |
| Block 5 [5.40-6.25] | Discussion/open problems |
July 5:
| Block 1 [1:50-2:35] | Avrim Blum On Routing without Regret |
|---|---|
| Block 2 [2:40-3:25] | Tim Roughgarden Computing (Correlated) Equilibria in Multi-Player Games |
| BREAK [3:25-4:00] | COFFEE BREAK |
| Block 3 [4:00-4.45] | Santosh Vempala Nash Equilibria in Random Games |
| Block 4 [4.50-5.35] | Michael Kearns [SEMI-PLENARY] The Effects of Network Structure on Equilibria and Computation |
| Block 5 [5.40-6.25] | Discussion/open problems |
July 6:
| Block 1 [1:50-2:35] | Anupam Gupta Metric Embeddings into l_1 and the Sparsest Cut Problem |
|---|---|
| Block 2 [2:40-3:25] | Avner Magen Metric Variance |
| BREAK [3:25-4:00] | COFFEE BREAK |
| Block 3 [4:00-4.45] | Yuval Rabani On Earthmover Distance, Metric Labeling, and 0-Extension |
| Block 4 [4.50-5.35] | Vijay Vazirani Adwords and Generalized Online Matching |
| Block 5 [5.40-6.25] | Piotr Indyk [SEMI-PLENARY] Approximations and streaming algorithms for geometric data |
Note: there will also be related plenary talks at the conference by Eva Tardos and Shang-Hua Teng.