IPCO X    

June 7 – 11, 2004

Columbia University




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
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)



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
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
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
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