Mon 6 Tue 7 Wed 8 Thu 9 Fri 10
Summerschool ILOG Workshop IPCO IPCO IPCO
Get-Together Party Conference Dinner

Summer School

Monday, June 6, 2005

9:00-12:00 Martin Dyer
Approximate Counting

Lecture Notes (PDF)
14:00-17:00 Daniel Spielman
Fast, Randomized Algorithms for Partitioning, Sparsification, and the Solution of Linear Systems

Lecture Notes (PDF)

Tuesday, June 7, 2005

9:00-12:00 Jiri Matousek
Generalized Linear Programming

Lecture Notes (PowerPoint)
14:00-17:45 ILOG-workshop
Between the summerschool and the conference, ILOG was hosting a half-day workshop. More information can be obtained from here.
Get-Together Party and check-in at TU Berlin
For more information see Social Events.


Speakers are highlighted.

Wednesday, June 8, 2005

08:30-10:30 Introduction
Matteo Fischetti, Cristiano Saturni:
Mixed-Integer Cuts from Cyclic Groups
Matteo Fischetti, Andrea Lodi:
Optimizing over the First Chvatal Closure
Yongpei Guan, Shabbir Ahmed, George L. Nemhauser:
Sequential Pairing of Mixed Integer Inequalities
11:00-12:30 Samuel Fiorini, Nadia Hardy, Bruce Reed, Adrian Vetta:
Approximate Min-Max Relations for Odd Cycles in Planar Graphs
Mohammad R. Salavatipour, Jacques Verstraete:
Disjoint Cycles: Integrality Gap, Hardness, and Approximation
Gyula Pap:
A Combinatorial Algorithm to Find a Maximum Even Factor
14:30-16:00 Fabian Chudak, Vania Eleuterio:
Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
Andreas Bley:
On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem
Retsef Levi, Joseph Geunes, H. Edwin Romeijn, David B. Shmoys:
Inventory and Facility Location Models with Market Selection
16:30-18:00 Anthony Man-Cho So, Jiawei Zhang, Yinyu Ye:
On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations
Nebojsa Gvozdenovic, Monique Laurent:
Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
Garud Iyengar, David Phillips, Cliff Stein:
Approximation Algorithms for Semidefinite Packing Problems with Applications to MAXCUT and Graph Coloring

Thursday, June 9, 2005

09:00-10:30 Jose R. Correa, Andreas S. Schulz, Nicolas Stier Moses:
On the Inefficiency of Equilibria in Congestion Games
Alexander Grigoriev, Maxim Sviridenko, Marc Uetz:
Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times
Jose R. Correa, Michael R. Wagner:
LP-Based Online Scheduling: From Single to Parallel Machines
11:00-12:30 Bernd Gärtner, Walter D. Morris Jr., Leo Rüst:
Unique Sink Orientations of Grids
Tibor Szabó, Ingo Schurr:
Jumping Doesn`t Help in Abstract Cubes
Naonori Kakimura, Satoru Iwata:
Computing the Inertia from Sign Patterns
14:30-16:30 Edoardo Amaldi, Pietro Belotti, Raphael Hauser:
Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem
Mohammad T. Hajiaghayi, Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov:
Power Optimization for Connectivity Problems
Heiko Röglin, Berthold Vöcking:
Smoothed Analysis of Integer Programming
Friedrich Eisenbrand, Gianpaolo Oriolo, Gautier Stauffer, Paolo Ventura:
Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs
17:30 Transfer to Schloss Cecilienhof (Potsdam)
evening Conference Dinner at Schloss Cecilienhof
(Place of the Potsdam Conference 1945)
At Schloss Cecilienhof a guided tour is offered.
Transfer back is organized by "shared taxis".
(Transfers, tour, and dinner are "all inclusive".)

Friday, June 10, 2005

09:00-10:30 Retsef Levi, Martin Pal, Robin Roundy, David B. Shmoys:
Approximation Algorithms for Stochastic Inventory Control Models
Kedar Dhamdhere, R. Ravi, Mohit Singh:
On Two-stage Stochastic Minimum Spanning Trees
Satoru Iwata, Ryo Shimizu:
Combinatorial Analysis of Generic Matrix Pencils
11:00-12:30 Lap Chi Lau:
Packing Steiner Forests
Alberto Caprara, Marco Locatelli, Michele Monaci:
Bidimensional Packing by Bilinear Programming
Andreas Brandstädt, Chinh T. Hoang:
On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
14:30-16:00 Harold Gabow:
On the L-infinity Norm of Extreme Points for Crossing Supermodular Directed Network LPs
Cor Hurkens, Judith Keijsper, Leen Stougie:
Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring Networks
Prabhakar Gubbala, Balaji Raghavachari:
Approximation Algorithms for Minimum Cardinality Two-Connected Spanning Subgraph Problem
16:30-18:00 Agustin Bompadre, James B. Orlin:
Using Grammars to Generate Very Large Scale Neighborhoods for the TSP and Other Sequencing Problems
William Cook, Daniel Espinoza, Marcos Goycoolea:
A Study of Domino-Parity and k-Parity Constraints for the TSP
Marcus Oswald, Gerhard Reinelt, Dirk Oliver Theis:
Not Every GTSP Facet Induces an STSP Facet

Pages maintained by Marc Pfetsch, last updated: June 14 2005