DIMACS Workshop Parallell Processing of Discrete Optimization Problems

April 28 - 29, 1994
DIMACS Center, Rutgers University, Piscataway, NJ

Organizers:

P.M. Pardalos, University of Florida, pardalos@math.ufl.edu

M.G.C. Resende, AT&T Bell Labs, mgcr@research.att.com

K.G. Ramakrishnan, AT&T Bell Labs, kgr@research.att.com

Workshop Program:

Thursday, April 28, 1994
     
9:00       Welcome from the DIMACS Director and the Organizers 
     
Session T.A  Chairman: P. Pardalos 
 

9:10       David Applegate, R. Bixby, V. Chvatal and W. Cook 
               Solving Large TSPs in Parallel 
  
9:45       Jonathan Eckstein 
               Parallel Branch-and-Bound Techniques for General Mixed Integer 
               Programming on the CM-5 
 
10:20      Jun Gu 
               Parallel Processing for Satisfiability (SAT) Problems 
     
10:55      Break 
     
Session T.B Chairman: M.G.C. Resende
 
     
11:15      Gerasoulis Apostolos 
               A Multistage Approach to Scheduling Task Graphs and its Impact 
               to Parallel Numerical Computing 

11:50      Christian Schutt and Jens Clausen 
               Parallel Algorithms for the Assignment Problem - An Experimental 
               Evaluation of 3 Distributed Algorithms 
     
12:25      Lunch 
     
    
Session T.C Chairman: K.G. Ramakrishnan
     
2:15       Per S. Laursen 
               Experiences with a Synchronous Parallel Branch and Bound Algorithm 

2:50       Reinhard Luling, Burkhard Monien, Stefan Tschoke 
               Load Balancing for Distributed Branch & Bound Algorithms: 
               Experiments and Theory 
    
3:25       George Karypis, Anshul Gupta, and Vipin Kumar 
               Parallel Formulation of Interior Point Algorithms 
     
4:00       Break 

 
Session T.D Chairman: P.M. Pardalos
     
4:20       Costas Busch and Marios Mavronicolas 
               Proving Correctness of Balancing Networks 

4:55       R. Correa and A. Ferreira 
               On (A)synchronous Parallel Branch-and-Bound 

5:30       Van-Dat Cung and Bertrand Le Cun 
               A Suitable Data Structure for Parallel A* 
     
7:00       Banquet 
     
 
 
Friday, April 29, 1994
     
Session F.A Chairman: M.G.C. Resende
     
9:00       Catherine Roucairol 
               Parallelism and Irregular Data Structures 

9:35       J. MacGregor Smith and Kui Xu 
               Serial & Parallel Algorithms for Quadratic Set Packing Problems 

10:10      Robert Meyer 
               Parallel Genetic Algorithms in Network Optimization 
     
10:45      Break 
     
Session F.B Chairman: K.G. Ramakrishnan
     
11:05      Shantanu Dutt and Nihar R. Mahapatra 
               New Anticipatory and Scalable Load Balancing Strategies for Parallel 
               Best First Search 

11:40      Santosh Pande and Kleanthis Psarris 
               Scheduling Acyclic Task Graphs on Distributed Memory Parallel 
               Architectures 

12:15      Alexander Reinefeld 
               Scalability of Massively Parallel Depth-First Search 
     
12:50      Lunch 
     
Session F.C Chairman: P. Pardalos
 
         
2:30       Andrea Clementi, Ludek Kucera and Jose Rolim 
               A Note on Parallel Randomized Algorithms for Searching Problems 

3:05       Jaideep Srivastava, Thomas M. Niccum and Bhaskar Himatsingka 
               Query Optimization and Processing in Parallel Databases 
     
3:40-4:00  Break 
 
 
Session F.D Chairman: M.G.C. Resende
 
     
4:00       Theodore Johnson 
               Asynchronous Distributed Data Structures: Lists and Priority Locks 
     
4:35       Boleslaw Mikolajczak 
               Parallel Distributed Algorithm to Compute all Homomorphisms 
               of Finite Atomata 
     
5:10       Zhijun Wu 
               E-Optimal Solutions to Nonlinear 0-1 Integer Programs Using 
               the Subgradient Algorithm 
     
5:45       Closing Remarks from the Organizers 
     
7:00       Dinner 
    

Previous: Participation

Workshop Index

DIMACS Homepage