ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAssignment ProblemsParallel Algorithm DesignParallel ComputationTask ParallelismAgent-task AssignmentLinear Assignment ProblemParallel BacktrackingParallel ProcessingTask Assignment
The linear assignment problem requires the determination of an optimal permutation vector for the assignment of tasks to agents. Even the backtracking implementation supports a rather powerful bounding function. Since the processing of permutation families (based on low-subscripted vector assignments) can be done independently of each other, one may examine parallel processing strategies, and discovery of instances in which the parallel execution is a very bad idea. Because of article size limitations, this article discusses only backtracking in parallel. A later article will address branch-and-bound in parallel.