PROGRAM

The DONET Summer School and the IPCO VIII Conference are hosted by the Institute of Computing and Information Sciences, Utrecht University. All lectures will take place at the Uithof Campus. For details on how to reach the various buildings on the Uithof Campus, please consult the page "Conference and summer school site".

Next to the lectures, the following events will take place at the Uithof Campus:



DONET Summer School
IPCO VIII




DONET Summer School on Integer and Combinatorial Optimization



Abstracts of the talks by Dan Bienstock: Abstracts of the talks by Éva Tardos:
Monday, June 11, Room: Transitorium 1 - Rood

08:45 - 09:45Summer School Registration outside room Transitorium 1 - Rood.
   
09:45 - 10:00 Welcome: Karen Aardal, Chair of the DONET - IPCO VIII Organizing Committee
10:00 - 11:00 Éva Tardos 1: "Techniques for approximation algorithms: Local search for a
 classification problem related to multi-way cuts"
11:00 - 11:30 Coffee & Tea
11:30 - 12:30 Dan Bienstock 1: "The maximum concurrent flow problem - a difficult
 combinatorial linear program that is easy to approximate"
   
12:30 - 14:00 Lunch in the Educatorium
   
14:00 - 15:00 Éva Tardos 2:"Approximation algorithms via linear programming: A general
  approach"
15:00 - 15:30 Coffee & Tea
15:30 - 16:30 Dan Bienstock 2: "A survey of provably good methods for approximately solving
 linear programs"
   
18:00 - ?? Summer School Dinner at Winkel van Sinkel, Oudegracht 158, in the old city center of Utrecht


Tuesday, June 12, Room: Aardwetenschappen - Kleine Collegezaal

10:00 - 11:00 Éva Tardos 3: "Approximation algorithms via primal-dual method: Some
 clustering problems"
11:00 - 11:30 Coffee & Tea
11:30 - 12:30 Éva Tardos 4: "Approximation algorithms in a game theoretic setting"
   
12:30 - 14:00 Lunch in the Educatorium
   
14:00 - 15:00 Dan Bienstock 3: " Oblivious rounding and derivatives
15:00 - 15:30 Coffee & Tea
15:30 - 16:30 Dan Bienstock 4: "Computational experiments with approximation algorithms for
 linear programming -- survey and new results"
   
17:00 - 18:30 Registration IPCO VIII, Centrumgebouw Noord, Padualaan 14, floor 0




IPCO VIII


Wednesday, June 13, Room: Unnikgebouw - 001

08:45 - 09:00 Welcome: Bert Gerards, Chair of the DONET - IPCO VIII Program Committee,
 Professor D. Siersma, Dean of the Faculty of Mathematics and Computer Science,
  Utrecht University
   
09:00 - 10:30 Session 1. Chairman: Egon Balas
09:00 - 09:30 Cornuéjols, Li: On the rank of mixed 0,1 polyhedra
09:30 - 10:00 Margot: Pruning by isomorphism in branch-and-cut
10:00 - 10:30 Eisenbrand, Rote: Fast 2-variable integer programming
   
10:30 - 11:00 Coffee & Tea
   
11:00 - 12:30 Session 2. Chairman: Éva Tardos
11:00 - 11:30 Guenin: Circuit Mengerian directed graphs
11:30 - 12:00 Frank, Király: Combined connectivity augmentation and orientation problems
12:00 - 12:30 Jackson, Jordan: Independence free graphs and vertex connectivity augmentation
   
12:30 - 14:00 Lunch in the Educatorium
   
14:00 - 15:00 Session 3. Chairman: Franz Rendl
14:00 - 14:30 Kodialam: The throughput of sequential testing
14:30 - 15:00 Hordijk, Van der Laan: Bounds for deterministic periodic routing sequences
   
15:00 - 15:30 Coffee & Tea
   
15:30 - 17:00 Session 4. Chairman: Jan Karel Lenstra
15:30 - 16:00 Chou, Queyranne, Simchi-Levi: The asymptotic performance ratio of an on-line
  algorithm for uniform parallel machine scheduling with release dates
16:00 - 16:30 Schuurman, Vredeveld: Performance guarantees of local search for multiprocessor
  scheduling
16:30 - 17:00 Queyranne, Sviridenko: A (2+epsilon)-approximation algorithm for generalized
  preemptive open shop problem with minsum criteria
   
18:00 - 20:00 IPCO Welcome Reception at the Academiegebouw, Zaal 1, Domplein 29, Utrecht

Thursday, June 14, Room: Transitorium 1 - Wit

09:00 - 10:30 Session 5. Chairman: Gérard Cornuéjols
09:00 - 09:30 Fleischer: A 2-approximation algorithm for (0,1,2) survivable network design
09:30 - 10:00 Hassin, Levin: Synthesis of 2-commodity flow networks
10:00 - 10:30 Garg, Khandekar, Konjevod, Ravi, Salman, Sinha: On the integrality gap of a
  natural formulation of the single-sink buy-at-bulk network design problem
   
10:30 - 11:00 Coffee & Tea
   
11:00 - 12:30 Session 6. Chairman: Monique Laurent
11:00 - 11:30 Halperin, Zwick: A unified framework for obtaining improved approximation
  algorithms for maximum graph bisection problems
11:30 - 12:00 Iyengar, Çezik: Cutting planes for mixed 0-1 semidefinite programming
12:00 - 12:30 Lasserre: An explicit exact SDP relaxation for nonlinear 0-1 programs
   
12:30 - 14:00 Lunch in the Educatorium
   
14:00 - 15:00 Session 7. Chairman: Gerhard Wöginger
14:00 - 14:30 Perregaard, Balas: Generating cuts from multiple-term disjunctions
14:30 - 15:00 Miller, Nemhauser, Savelsbergh: Facets and polyhedral characterizations for a
  multi-item production planning model with setup times
   
15:00 - 15:30 Coffee & Tea
   
15:30 - 17:00 Session 8. Chairman: Bob Bixby
15:30 - 16:00 Sebö, Tannier: Connected joins in graphs
16:00 - 16:30 Frank, Szegö: An extension of a theorem of Henneberg and Laman
16:30 - 17:00 Guenin: Integral polyhedra related to even cycle and even cut matroids
   
18:00 - ?? IPCO Conference Dinner at Houtzaagmolen De Ster, Molenpark 3, Utrecht

Friday, June 15, Room: Unnikgebouw - 001

09:00 - 10:30 Session 9. Chairman: David Williamson
09:00 - 09:30 Azar, Regev: Strongly polynomial algorithms for the unsplittable flow problem
09:30 - 10:00 Elkin, Peleg: Approximating k-spanner problems for k>2
10:00 - 10:30 Archer: Two O(log^{*k})-approximation algorithms for the asymmetric k-center
  problem
   
10:30 - 11:00 Coffee & Tea
   
11:00 - 12:30 Session 10. Chairman: Michel Goemans
11:00 - 11:30 Fleiner: A matroid-generalization of the stable matching polytope
11:30 - 12:00 Cheriyan, Vempala: Edge coverings of set-pairs
12:00 - 12:30 Fujishige, Iwata: Bisubmodular function minimization
   
12:30 - 14:00 Lunch in the Educatorium
   
14:00 - 15:00 Session 11. Chairman: Andras Sebö
14:00 - 14:30 Sitters: On the complexity of preemptive scheduling on unrelated machines
14:30 - 15:00 Newman, Vempala: On the maximum acyclic subgraph problem
   
15:00 - 15:30Coffee & Tea
   
15:30 - 16:30 Session 12. Chairman: Andras Frank
15:30 - 16:00 Stein, Wagner: Approximation algorithms for the minimum bends traveling
  salesman problem
16:00 - 16:30 Chudak, Roughgarden, Williamson: Approximate k-MSTs and k-Steiner trees via
  the primal-dual method and Lagrangean relaxation
   
16:30 - 16:45 Closing


Back to the IPCO VIII Conference home page.

Page maintained by Karen Aardal. Updated June 7, 2001.