Program Local information Travel Information Registration
Sponsors About the conference About the summer school Hotel information
Related events Program committee Organizing committee Contact




Proceedings
IPCO 2002 Logo

Infinite Buffet in the Infinite Corridor, MIT


Program

Summer School

The activities will take place in Lecture Hall 6-120 (map it) (see pictures)

Saturday, May 25, 2002

08:45 - 09:00Welcome
09:00 - 10:15Robust Discrete Optimization, Lecture I
10:15 - 10:45Coffee Break
10:45 - 12:00Robust Discrete Optimization, Lecture II
12:00 - 13:15Lunch Break
13:15 - 14:30Set-Pair Formulations for Network Design, Lecture I
14:30 - 16:30Robust Discrete Optimization, Exercises
16:30 - 16:45Coffee Break
16:45 - 18:00Set-Pair Formulations for Network Design, Lecture II
18:00 - 18:15Break
18:15 - 19:15Robust Discrete Optimization, Discussion
19:30 - 23:30Summer School Party, Eastgate Penthouse


Sunday, May 26, 2002

08:45 - 10:00Randomized Algorithms for Cut and Flow Problems, Lecture I
10:00 - 10:30Coffee Break
10:30 - 12:30Set-Pair Formulations for Network Design, Exercises
12:30 - 13:30Lunch Break
13:30 - 14:45Randomized Algorithms for Cut and Flow Problems, Lecture II
14:45 - 16:45Randomized Algorithms for Cut and Flow Problems, Exercises
16:45 - 17:00Coffee Break
17:00 - 19:00Set-Pair Formulations for Network Design and Randomized Algorithms for Cut and Flow Problems, Discussion


IPCO Conference

(see pictures)

Sunday, May 26, 2002

18:00 - 21:00Informal Get-together/On-Site Registration, MIT Museum (map it)


All sessions will take place in the Wong Auditorium (E51-115), Tang Center (map it)

Monday, May 27, 2002

08:00 - 08:45Continental Breakfast/On-Site Registration
08:45 - 09:00Opening Ceremony
09:00 - 10:30Satoru Iwata: A faster scaling algorithm for minimizing submodular functions
Bianca Spille, Robert Weismantel: A generalization of Edmonds' matching and matroid intersection algorithms
Akihisa Tamura: Coordinatewise domain scaling algorithm for M-convex function minimization
10:30 - 11:00Coffee Break
11:00 - 12:30Lisa Fleischer, Martin Skutella: The quickest multicommodity flow problem
Oktay Günlük: A new min-cut max-flow ratio for multicommodity flows
Michael Lewin, Dror Livnat, Uri Zwick: Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems
12:30 - 14:30Lunch, MIT Faculty Club
14:30 - 16:00Sylvia Boyd, Geneviève Labonté: Finding the exact integrality gap for small travelling salesman problems
Adam N. Letchford, Andrea Lodi: Polynomial-time separation of simple comb inequalities
Klaus M. Wenger: A new approach to cactus construction applied to TSP support graphs
16:00 - 16:30Coffee Break
16:30 - 18:00Kent Andersen, Gérard Cornuéjols, Yanjun Li: Split closure and intersection cuts
Sanjeeb Dash: An exponential lower bound on the length of some classes of branch-and-cut proofs
Jean-Philippe P. Richard, Ismael Regis de Farias, Jr., George L. Nemhauser: Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms
18:00 - 20:00Welcoming Reception, Charles Diebold III Lounge, Tang Center


Tuesday, May 28, 2002

08:15 - 09:00Continental Breakfast/On-Site Registration
09:00 - 10:30Ron Aharoni, Tamás Fleiner: On a lemma of Scarf
Bertrand Guenin: A short proof of Seymour's characterization of the matroids with the max-flow min-cut property
Jay Sethuraman, Chung-Piaw Teo, Rakesh V. Vohra: Integer programming and Arrovian social welfare functions
10:30 - 11:00Coffee Break
11:00 - 12:30Ramamoorthi Ravi, Amitabh Sinha: Integrated logistics: Approximation algorithms combining facility location and network design
René Sitters: The minimum latency problem is NP-hard for weighted trees
Maxim Sviridenko: An improved approximation algorithm for the metric uncapacitated facility location problem
12:30 - 14:30Lunch Break
14:30 - 16:00Ernst Althaus, Christian Fink: A polyhedral approach to surface reconstruction from planar contours
Andreas Eisenblätter: The semidefinite relaxation of the k-partition polytope is strong
Ismael Regis de Farias, Jr., George L. Nemhauser: A polyhedral study of the cardinality constrained knapsack problem
16:00 - 16:30Coffee Break
16:30 - 18:00Mao-Cheng Cai, Xiaotie Deng, Haodi Feng, Guojun Li, Guizhen L: A PTAS for minimizing total completion time of bounded batch scheduling
Alberto Caprara, Andrea Lodi, Michele Monaci: An approximation scheme for the two-stage, two-dimensional bin packing problem
Klaus Jansen, Lorant Porkolab: On preemptive resource constrained scheduling: Polynomial-time approximation schemes
18:30 - 23:00Conference Dinner, Fogg Art Museum


Wednesday, May 29, 2002

08:15 - 09:00Continental Breakfast
09:00 - 10:30Karen Aardal, Arjen K. Lenstra: Hard equality constrained integer knapsacks
Alexander Barvinok, Tamon Stephen: The distribution of values in the quadratic assignment problem
Diego Klabjan: A new subadditive approach to integer programming
10:30 - 11:00Coffee Break
11:00 - 12:30Gruia Calinescu, Amit Chakrabarti, Howard Karloff, Yuval Rabani: Improved approximation algorithms for resource allocation
Ari Freund, Joseph (Seffi) Naor: Approximating the advertisement placement problem
Rajiv Gandhi, Samir Khuller, Yoo-Ah Kim, Yung-Chun (Justin) Wan: Algorithms for minimizing response time in broadcast scheduling
12:30 - 13:30Lunch Break
13:30 - 15:00Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph (Seffi) Naor, Danny Raz: Building edge-failure resilient networks
Bruce Shepherd, Adrian Vetta: The demand matching problem
Kunal Talwar: Single-sink buy-at-bulk LP has constant integrality gap
15:00 - 15:15Closing Ceremony


All accepted papers are published in Volume 2337 of Springer's Lecture Notes in Computer Science Series.


Back to the IPCO 2002 Conference home page.

mit Comments and questions to ipco2002@mit.edu. Page maintained by Nicolas Stier. Last updated Tue May 28 00:13:08 EDT 2002.