**DIMACS - Series in Discrete Mathematics and Theoretical Computer Science**

Volume: 22;
1995;
374 pp;
Hardcover

MSC: Primary 68; 90;

Print ISBN: 978-0-8218-0240-3

Product Code: DIMACS/22

List Price: $114.00

Individual Member Price: $91.20

**Electronic ISBN: 978-1-4704-3980-4
Product Code: DIMACS/22.E**

List Price: $114.00

Individual Member Price: $91.20

# Parallel Processing of Discrete Optimization Problems

Share this page *Edited by *
*Panos M. Pardalos; Mauricio G. C. Resende; K. G. Ramakrishnan*

A co-publication of the AMS and DIMACS

This book contains papers presented at the Workshop on Parallel Processing of Discrete Optimization Problems held at DIMACS in April 1994. The contents cover a wide spectrum of the most recent algorithms and applications in parallel processing of discrete optimization and related problems. Topics include parallel branch and bound algorithms, scalability, load balancing, parallelism and irregular data structures and scheduling task graphs on parallel machines. Applications include parallel algorithms for solving satisfiability problems, location problems, linear programming, quadratic and linear assignment problems. This book would be suitable as a textbook in advanced courses on parallel algorithms and combinatorial optimization.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

#### Table of Contents

# Table of Contents

## Parallel Processing of Discrete Optimization Problems

- Cover Cover11
- Title page v6
- Contents vii8
- Quote ix10
- Foreword xi12
- Preface xiii14
- Proving correctness for balancing networks 116
- A note on parallel randomized algorithms for searching problems 3348
- Modeling parallel branch-and-bound for asynchronous implementations 4560
- A data parallel space dilation algorithm for the concentrator location problem 5772
- A multistage approach for scheduling task graphs on parallel machines 8196
- Parallel algorithms for satisfiability (SAT) problem 105120
- Experiences with a parallel formulation of an interior point algorithm 163178
- Experiences with a synchronous parallel branch and bound algorithm 181196
- New anticipatory load balancing strategies for parallel A* algorithms 197212
- A parallel algorithm for computing all homomorphisms of deterministic finite automata 233248
- Query optimization and processing in parallel databases 259274
- Scheduling acyclic task graphs on distributed memory parallel architectures 289304
- Scalability of massively parallel depth-first search 305320
- On irregular data structures and asynchronous parallel branch and bound algorithms 323338
- Parallel algorithms for the assignment problem–An experimental evaluation of three distributed algorithms 337352
- Serial & parallel algorithms for QSP problems 353368
- Back Cover Back Cover1390

#### Readership

Graduate students and researchers in computer science, mathematics, engineering, and operations research.