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, 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
Index
DIMACS Homepage