DIMACS Workshop on Network Design: Connectivity and Facilities Location

April 28-30, 1997
Nassau Inn, Senior Room, Palmer Square, Princeton, NJ

Organizers: Ding-Zhu Du (, Panos Pardalos (

Advisory Committee: P. Berman, R. Burkard, A.V. Goldberg, F.K. Hwang, M. Karpinski, Robert E. Tarjan, H. Rubinstein, A.C. Yao.

Tentative Program
Monday, April 28, 1997

Session 1   (Chair Panos M. Pardalos)

 8:45- 9:30   S. Arora
              "Nearly Linear Time Approximation Schemes for
              Euclidean TSP and Other Geometric Problems"

 9:30-10:00   Break

Session 2   (Chair Ding-Zhu Du)

10:00-10:30   Marek Karpinski and Alexander Zelikovsky
              "Approximation for Steiner trees in dense graphs"

10:30-11:00   Stefan Voss and Kai Gutenschwager,
              "A Chunking based genetic algorithm for the
              Steiner tree problem in graphs"

11:00-11:30   Piotr Berman and Alexander Zelikovsky
              "On the  Power-$p$ and Bottleneck Steiner Tree Problems"

11:30-12:00   J. H. Rubinstein, M. Brazil, D. Thomas, J. Weng, 
	      and N. Wormald
              "Shortest Networks on Spheres"

12:00- 2:00   lunch

Session 3 (Chair Piotr Berman)

 2:00- 2:30   J. F. Weng
              "A New Model of Generalised Steiner Networks"

 2:30- 3:00   Doreen Thomas
              "Gradient Constrained Minimal Steiner Trees"

 3:00- 3:30   Dietmar Cieslik,
              "Using of Hadwiger Numbers in Network Design"

 3:30- 4:00   Break

Session 4 (Chair J.F. Weng)

 4:00- 4:30   S. Cheng,
              "The Steiner Tree Problem for Terminals on the
              Boundary of a Rectilinear Polygon"

 4:30- 5:00   Klaus Jansen and Thomas Erlebach
              "Approximation results for the optimum cost
              chromatic partition problem"

 5:00- 5:30   Narsingh Deo and Nishit Kumar,
              "Constrained Spanning Tree Problems:
              Fast Approximate Methods and Parallel Computation"

 5:40- 8:30   Reception
              Prospect Gardens
              Drawing Room & Terrace
              Princeton Campus

Tuesday, April 29, 1997 Session 5 (Chair Ding-Zhu Du) 8:30- 9:00 David Shmoys, Eva Tardos, Karen Aardal, "Approximation Algorithms for Facility Location Problems" 9:00- 9:30 Francisco Barahona and David Jensen "Plant location with minimum inventory" 9:30-10:00 Wu-ji Li and J.MacGregor Smith "Star, Grid, and Ring Topologies in Facility Location and Network Design" 10:00-10:30 Break Session 6 (Chair Panos M. Pardalos) 10:30-11:00 Warren B. Powell, Zhi-Long Chen, Greg Godfrey, Joel Shapiro "Massive Dynamic Decomposition Methods for Dynamic Network Flows" 11:00-11:30 Guoliang Xue "Optimal Routing in Communication Systems with Channel Capacities and Channel Reliabilities" 11:30-12:00 Roberto Battiti and Alan Bertossi "Greedy and prohibition-based diversification heuristics for Graph Partitioning" 12:00- 2:00 lunch Session 7 (Chair Guo-Liang Xue) 2:00- 2:30 Andreas Eisenblaetter "A Frequency Assignment Problem in Cellular Phone Networks" 2:30- 3:00 Roland Wessaely and Martin Groetschel "Dimensioning of survivable telecommunication networks" 3:00- 3:30 S. Raghavan and T.L. Magnanti "Strong formulations for network design with connectivity requirements" 3:30- 4:00 Break Session 8 (Chair Pengjun Wan) 4:00- 4:30 Samir Khuller "Approximation Algorithms for Dynamic K-Center Problems" 4:30- 5:00 Jose D. P. Rolim and Luca Trevisan "A Case Study of Derandomization Methods for Combinatorial Approximation Algorithms" 5:00- 5:30 Cees Duin "An reduction based algorithm for the Steiner problem in graphs" 6:00-10:00 Banquet, followed by panel discussion Prospect Gardens Princeton Campus Presidential Dining Room
Wednesday, April 30, 1997 Session 5 (Chair Panos M. Pardalos) 8:30- 9:00 Rainer E. Burkard and Jakob Krarup "A linear algorithm for the 1-median problem on a cactus with positive and negative weights" 9:00- 9:30 Jianer Chen "Network Parallel Routing and Maximum Partition Matching" 9:30-10:00 Feng Cao*, D. Z. Du, and F. D. Hsu "Fault-tolerant Routing and Multicasting in Butterfly Networks" 10:00-10:30 Break Session 6 (Chair Ding-Zhu Du) 10:30-11:00 Ramamoorthi Ravi "Service-Constrained Network Design Problems" 11:00-11:30 Robert R. Meyer "Genetic Algorithms and Multi-Coordination in Network Design" 11:30-12:00 S. Raghavan and T.L. Magnanti "A Dual-Ascent Approach to Low-Connectivity Network Design" 12:00- 2:00 lunch Session 7 (Chair Mauricio Resende) 2:00- 2:30 Klaus Jansen "Wavelength allocation in optical networks" 2:30- 3:00 Pengjun Wan "Several Isuues in Optical Networks" 3:00- 3:30 C.S. Adjiman, C.A. Schweiger, and C.A. Floudas "Nonlinear and Mixed-Integer Optimization in Process Network Systems" 3:30- 4:00 Break Session 8 (Chair C.A. Floudas) 4:00- 4:30 R. A. Murphey and P. M. Pardalos and L. Pitsoulis "A GRASP For The MultiTarget MultiSensor Tracking Problem" 4:30- 5:00 Mauricio Resende "Computing approximate solution to the maximum covering problem with GRASP" 5:00- 5:30 Kristina Holmqvist, Athanasios Migdalas* and Panos M. Pardalos "A GRASP Algorithm for the Single Source Uncapacitated Minimum Concave-Cost Network Flow Problem" 5:30-6:00 Madhav Marathe "Network Improvement Problems"

Previous: Participation
Next: Registration
DIMACS Homepage
Contacting the Center
Document last modified on October 22, 1998.