IPCO X

June 7 – 11, 2004

Columbia University

Program

All IPCO lectures will take place at Davis Auditorium, located in the Schapiro (CEPSR) building. The Summer School lectures will take place at 415 CEPSR.

Please note: the IPCO X proceedings have been published by Springer as Lecture Notes in Computer Science, Volume 3064 .

IPCO Summer School

	Monday, June 7, 2004
8:00 - 9:00	Coffee, Summer School Registration
9:00 - 9:15	Welcome
9:15 - 10:45	Joan Feigenbaum: Incentives and Internet Computation, I
10:45 - 11:00	Coffee break
11:00 - 12:30	Joan Feigenbaum: Incentives and Internet Computation, II
12:30 - 2:00	Lunch break
2:00 - 3:30	Rakesh Vohra: Linear Inequalities and Mechanism Design, I
3:30 - 4:00	Coffee break
4:00 - 5:30	Rakesh Vohra: Linear Inequalities and Mechanism Design, II

	Tuesday, June 8, 2004
9:00 - 10:30	Tim Roughgarden: The Price of Anarchy, I
10:30 - 11:00	Coffee break
11:00 - 12:30	Tim Roughgarden: The Price of Anarchy, II
3:00 PM -	Guided Tour of the Met ($16 pp., details provided at the conference)

IPCO X

	Wednesday, June 9, 2004
8:00 - 8:45	Coffee, on-site registration
8:45 - 9:00	Opening remarks
9:10 -10:30	Session 1 Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem R. Fukasawa, J. Lysgaard, M. Poggi de Aragao, M. Reis, E. Uchoa and R. Werneck Metric inequalities and the network loading problem P. Avella, S. Mattia and A. Sassano Valid inequalities based on simple mixed-integer sets S. Dash and O. Günlük
10:30-11:00	Coffee break
11:00 -12:30	Session 2 The "Price of Anarchy" when costs are non-separable and asymmetric G. Perakis Computational complexity, fairness, and the price of anarchy of the maximum latency problem J.R. Correa, A. Schulz and N.E. Stier Moses Polynomial Time Algorithm for Determining Optimal Strategies in Cyclic Games D. Lozovanu
12:30 - 2:30	Lunch
2:30 - 4:00	Session 3 A robust optimization approach to supply chain management D. Bertsimas and A. Thiele Hedging uncertainty: approximation algorithms for stochastic optimization problems R. Ravi and A. Sinha Scheduling an Industrial Production Facility E. Asgeirsson, J. Berry, C. Phillips, D. Phillips, C. Stein and J. Wein
4:00 - 4:30	Coffee break
4:30 - 6:00	Session 4 Three min-max theorems concerning cyclic orders of strong digraphs. A proof of a conjecture of Gallai S. Bessy and S. Thomassé A TDI description of Restricted 2-Matching Polytopes G. Pap Enumerating minimal dicuts and strongly connected subgraphs and related geometric problems E. Boros, K. Elbassioni, V. Gurvich and L. Khachiyan
6:00 - 8:00	Reception (Carleton Lounge)

	Thursday, June 10, 2004
8:15 - 9:00	Coffee, on-site registration
9:00- 10:30	Session 5 Semi-continuous cuts for mixed-integer programming I.R. de Farias, Jr. Combinatorial Benders' cuts G. Codato and M. Fischetti A faster exact separation algorithm for blossom inequalities A.N. Letchford, G. Reinelt and D.O. Theis
10:30 -11:00	Coffee break
11:00- 12:30	Session 6 LP-based approximation algorithms for capacitated facility location R. Levi, D. Shmoys and C. Swamy A multi-exchange local search algorithm for the capacitated facility location problem J. Zhang B. Chen and Y. Ye Separable concave optimization approximately equals piecewise linear optimization T.L. Magnanti and D. Stratila
12:30- 2:30	Lunch break
2:30- 4:00	Session 7 Three kinds of integer programming algorithms based on Barvinok's rational functions J.A. De Loera, D. Haws, R. Hemmecke, P. Huggins and R. Yoshida The path-packing structure of graphs A. Sebö and L. Szego More on a Binary-Encoded Coloring Formulation J. Lee and F. Margot
4:00- 4:30	Coffee break
4:30- 5:30	Session 8 Single machine scheduling with precedence constraints J.R. Correa and A. Schulz The constrained minimum weighted sum of job completion times problem A. Levin and G.J. Woeginger
7:00 - 10:00	Conference Dinner (Faculty House) -- co-sponsored by IBM and MPS

	Friday, June 11, 2004
8:15 - 9:00	Coffee, on-site registration
9:00- 10:30	Session 9 Near-optimum global routing with coupling, delay bounds, and power consumption J. Vygen A flow-based method for improving the expansion or conductance of graph cuts K. Lang and S. Rao All rational polytopes are transportation polytopes and all polytopal integer sets are contingency tables S. Onn and J. De Loera
10:30 -11:00	Coffee break
11:00- 12:30	Session 10 A capacity scaling algorithm for M-convex submodular flow S. Iwata, S. Moriguchi and K. Murota The path-packing structure of graphs A. Sebö and L. Szego (RESCHEDULED) Minsquare factors and maxfix covers of graphs N. Apollonio and A. Sebö
12:30- 2:30	Lunch break
2:30- 4:00	Session 11 Optimizing over semimetric polytopes A. Lodi, A. Frangioni and R. Rinaldi On polyhedra defined by even factors T. Király and M. Makai Low-dimensional faces of random 0/1 polytopes V. Kaibel