Browse Prior Art Database

Parallel Algorithms for the Assignment Problem

IP.com Disclosure Number: IPCOM000128317D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 14 page(s) / 33K

Publishing Venue

Software Patent Institute

Related People

Sajal K. Das: AUTHOR [+4]

Abstract

Using an EREW PRAM model with a fixed number p of processors, we present two optimal parallel algorithms to solve an n x n assignment problem. The first algo- _13 rithm, a parallelization of the Hungarian method, runs in [Equation ommitted] time and achieves the optimal speedup using [Equation ommitted] processors. The second algorithm log n 3 works by finding a min-cost flow in an appropriate network in [Equation ommitted] time, P and is optimal for [Equation ommitted] The product processor-(time)2 is identified as a perfor-mance parameter to derive the optimality conditions. Key Words and Phrases: EREW PRAM, parallel algorithms, assignment problem, bipartite weighted matching

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Parallel Algorithms for the Assignment Problem

by

Sajal K. Das and Narsingh Deo

CS-TR-87-15 - July PARALLEL ALGORITHMS FOR THE ASSIGNMENT PROBLEM

Sajal K. Das

Narsingh Deo

Department of Computer Science University of Central Florida Orlando, FL 32816, U.S.A.

ABSTRACT

Using an EREW PRAM model with a fixed number p of processors, we present two optimal parallel algorithms to solve an n x n assignment problem. The first algo-

_13 rithm, a parallelization of the Hungarian method, runs in

(Equation Omitted)

time and

achieves the optimal speedup using

(Equation Omitted)

processors. The second algorithm log n

3 works by finding a min-cost flow in an appropriate network in

(Equation Omitted)

time, P and is optimal for

(Equation Omitted)

The product processor-(time)2 is identified as a perfor-mance parameter to derive the optimality conditions.

Key Words and Phrases: EREW PRAM, parallel algorithms, assignment problem, bipartite weighted matching

1. INTRODUCTION

University of Central Florida Page 1 Dec 31, 1987

Page 2 of 14

Parallel Algorithms for the Assignment Problem

The assignment problem (also known as the minimum-weight matching in a bipar-tite graph) is an important combinatorial optimization problem, which often requires fast solution. Informally, the problem is to find a minimum-cost assignment of n workers to n jobs in a one-to-one fashion, where the assignment of a worker Wi to a job Jj is associated with a nonnegative cost tij. In order to build a mathematical model, let us define the variables

1, if Wi is assigned to

(Equation Omitted)

otherwise.

Formally, the assignment problem is defined as:

(Equation Omitted)

(Equation Omitted)

If the workers and jobs are not equal in number, we introduce dummy workers or jobs such that the cost associated with a dummy is zero. This is called a balanced assign-ment problem, and the corresponding weighted bipartite graph is complete.

The assignment problem can be solved by the Hungarian method [4] or by finding a min-cost flow in an appropriate network [2] --- each requiring

(Equation Omitted)

. The best-known sequential algorithm due to Galil, Micali and Gabow [1] has the time complexity of

(Equation Omitted)

-node bipartite graph of m edges. Though better for sparse graphs, this algorithm does not appear to be easily parallelizable. We observe that the Hungarian and the min-cost flow algorithm have potential parallelism and are efficient for dense graphs. In comparison with many other polynomial-time-solvable graph problems [5], virtually no attempt has been made to design parallel algorithms for the assignment problem. This paper presents two parallel algorithms for solving this problem and analyzes their performance. Our parallel computation model is an exclusive-read and exclusive-write (EREW) parallel random access memory (PRAM) consisting of a fixed number p :5 n of pro-cessors, each equipped with a local memory and a pro...