DIMACS Workshop on Network Design: Connectivity and Facilities Location

Nassau Inn, Senior Room, Palmer Square, Princeton, NJ

Organizers: Ding-Zhu Du (dzd@cs.umn.edu), Panos Pardalos (pardalos@ufl.edu)

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

Monday, April 28, 1997Session 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 BreakSession 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 lunchSession 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 BreakSession 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, 1997Session 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 BreakSession 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 lunchSession 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 BreakSession 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, 1997Session 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 BreakSession 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 lunchSession 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 BreakSession 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

Index

DIMACS Homepage

Contacting the Center

Document last modified on October 22, 1998.