Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

Search Algorithms for Discrete Optimization Problems

• Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

• To accompany the text ``Introduction to Parallel Computing'',

• Addison Wesley, 2003.

Topic Overview

• Discrete Optimization - Basics

• Sequential Search Algorithms

• Parallel Depth-First Search

• Parallel Best-First Search

• Speedup Anomalies in Parallel Search Algorithms

Discrete Optimization - Basics

• Discrete optimization forms a class of computationally expensive problems of significant theoretical and practical interest.

• Search algorithms systematically search the space of possible solutions subject to constraints.

Definitions

•