Discrete Mathematics and Theoretical Computer Science

TITLE: Workshop on Parallel Processing of Discrete Optimization Problems

EDITORS: Panos M. Pardalos, Mauricio G.C. Resende, K.G. Ramakrishnan

Published by the American Mathematical Society

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

Discrete optimization problems (

Formally, a * dop* can be stated as follows:
*
Given a finite discrete set X and
a function $$ f(x) defined on the elements of X,
find an optimal element $$ x^{*}, such that,
$$ f(x^{*}) = min{f(x) | x &epsilon X }.*
In certain problems, the aim is to find any member of the set

Given that many classes of * dop* are NP-hard, one may argue that
there is no point in applying parallel processing to these
problems, as the worst-case run time can never
be reduced to a polynomial unless we have
an exponential number of processors. However, the average time
complexity of heuristic search algorithms for many problems is
polynomial.
Also, there are some heuristic search algorithms which find
suboptimal solutions in
polynomial time
(e.g., for certain problems,
approximate branch-and-bound algorithms are known to run in
polynomial time).
In these cases, parallel processing can
significantly increase the size of solvable problems.
Some applications using search algorithms (e.g.
robot motion planning,
task scheduling)
require real time solutions. For these applications, parallel
processing is perhaps the only way to obtain acceptable performance.
For some problems, optimal solutions are highly desirable, and
cab be obtained for moderate
sized instances in a reasonable amount of time using parallel search techniques
(e.g. vlsi floor-plan optimization).

Parallel computers having thousands of processing elements are now commercially available. The cost of these machines is similar to that of large mainframes, but they offer significantly more raw computing power. Due to advances in vlsi technology and economies of scale, the cose of these machines is expected to go down drastically over the next decade. It may soon be possible to construct computers comprising thousands to millions of processing elements at costs ranging from those of high-end workstations to large mainframes. This technology has created substantial interest in exploring the use of parallel processing for search based applications.

In the context of the 1993-1994 DIMACS special year on parallel computing, a two-day workshop entitled "Parallel Processing of Discrete Optimization Problems" was held on April 28-29. The workshop featured about twenty invited speakers from Europe and North America. This volume contains a collection of refereed papers from the workshop. The papers cover a wide spectrum of algorithms and applications in parallel processing of discrete optimization and related problems.

One of the key successes of the workshop was that collaboration started among the European group of researchers working on the scoop project (Solving Combinatorial Optimization Problems in Parallel) and researchers from U.S. In addition, many participants stayed at DIMACS after the workshop working on joint projects.

The workshop was sponsored by DIMACS with funds from National Science Foundation and The New Jersey Commission on Science and Technology. We would like to take this opportunity to thank the sponsors, the DIMACS staff, the participants, the authors, the referees, and the American Mathematical Society, for making the workshop successful and the publication of this volume possible.

Panos M. Pardalos, Mauricio G.C. Resende, and K.G. Ramakrishnan

December 1994

Foreword xi Preface xiii Proving Correctness for Balancing Networks Costas Busch and Marios Mavronicolas 1 A Note on Parallel Randomized Algorithms for Searching Porblems Andrea Clemnti, Jose Rolim and Ludek Kucera 33 Modeling Parallel Branch-and-Bound for Asynchronoous Implementations Ricardo Correa and Afonso Ferreira 45 A Data Parallel Space Dilation Algorithm for the Concentrator Location Problem Olof Damberg and Athanasios Migdalas 57 A Multistage Approach for Scheduling Task Graphs on Parallel Machines Apostolos Gerasoulis, Jia Jiao and Tao Yang 81 Parallel Algorithms for Satisfiability (SAT) Problem Jun Gu 105 Experiences with a Parallel Formulation of an Interior Point Algorithm George Karypis, Anshul Gupta and Vipin Kumar 163 Experiences with a Synchronous Parallel Branch and Bound Algorithm Per S. Laursen 181 New Anticipatory Load Balancing Strategies for Parallel A* Algorithms Nihar R. Mahapatra and Shantanu Dutt 197 A Parallel Algorithm for Computing all Homomorphisms of Deterministic Finite Automata Boleslaw Mikolajczak 233 Query Optimization and Processing in Parallel Databases T.M. Niccum, J. Srivastava, B. Himatsingka and J. Li 259 Scheduling Acyclic Task Graphs on Distributed Memory Parallel Architectures Santos Pande and Kleanthis Psarris 289 Sclability of Massively Parallel Depth-First Search Alexander Reinefeld 305 On Irregular Data Structures and Asynchronous Parallel Brand and Bound Algorithms Catherine Roucairol 323 Parallel Algorithms for the Assignment Problem - An Experimental Evaluation of Three Distributed Algorithms Christian Schutt and Jens Clausen 337 Serial & Parallel Algorithms for QSP Problems J. MacGregor Smith and Jui Xu 353

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.