Design and Analysis of Algorithms

Prev

Next

Optimization Problems

Optimization problems refers to the class of problems where the goal is to maximize or minimize the solution. i.e. Among the several solutions, possibly exponential, choose the one that is best based on some particular criteria.

Examples

1. Task scheduling: Given a set of tasks and the duration required to complete each of them, what is the best way to schedule them so as to minimize the average completion time?

2. Knapsack: Given a set of items, each of which has certain weight (w_i) and benefit (b_i), and a knapsack of capacity W, what is the best way to fill the knapsack so as to maximize the benefit?

3. Chain Matrix Multiplication: Given a chain of matrices, each of which has the dimension d_i-1 x d_i, what is the best way to multiply them so as to minimize the number of overall multiplications.

4. Maximum Subsequence Sum: Given an array of numbers, that possibly includes negative values, determine the particular subsequence whose sum the maximum.

5. Longest Common Subsequence: Given two strings of same or different lengths, find the longest common subsequence.

6. Optimal Binary Search Trees: Given a set of keys, with probability of search queries for each key, what is the best way to form a binary search tree of the keys so as to minimize the overall cost answering the search queries?

7. Data Compression: Given a set of symbols, with the probability of occurrence of each symbol in a document, what is the best way to encode the document so as to achieve maximum compression?

8. Minimum Spanning Tree: Given an undirected graph of certain number of vertices and edges with certain weights, what is the smallest weighted spanning tree that connects all the vertices of the graph.

9. Shortest path: Given a graph of certain number of vertices and edges with certain weights, determine the shortest path from a node to another node.

10. Travelling Salesman: Given a set of nodes, denoting cities, and the edges between the nodes, denoting the distances between the cities, what is the best way for a salesman to visit all the nodes exactly once and come back to the starting node?

While the above list gives the flavor of optimization problems, it is by no means exhaustive. There exists countless such problems. What we are going to learn are some standard algorithmic strategies that are employed to handle them. The strategies include the following in the order of preference:

• 1. Greedy strategy: This is the most preferred strategy applied when the following properties hold.
  
  1. Optimal substructure
  2. Greedy choice property


• 2. Dynamic programming: Dynamic programming is a "systematic brute-force" technique that avoids solving same subproblems again through a bottom-up approach. This is applied when greedy choice property does not hold.
  
  1. Optimal substructure
  2. Overlapping subproblems

If a problem does not exhibit overlapping subproblems property too, dynamic programming solution will be as inefficient as the brute-force solution. This is not an issue if the solution takes polynomial time. However, if it takes exponential time, we need to compromise and settle for a suboptimal solution. The following strategies are applied in such cases.

• 3. Branch-and-bound: This is a heuristic based technique wherein the search is pruned at every stage and some search paths are eliminated based on a promising criteria. It could be possible that we eliminate the path towards best solution leading to a sub-optimal solution. Branch-and-bound strategy usually guarantees that solution obtained is not worse than the optimal solution by a certain factor.


• 4. Backtracking: Backtracking is another strategy where in the search paths are explored upto a certain depth and if optimal solution is not found, it backtracks searches other paths.

Definitions

Optimal substructure: The optimal solution to a problem contains within itself optimal solutions to its subproblems.

Greedy choice property: Locally optimal solutions leads to globally optimum solution.

Overlapping subproblems: Breaking down the problem recursively leads to several subproblems that are the same.