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